1. A sharp upper bound for the harmonious total chromatic number of graphs and multigraphsMarién Abreu, John Baptist Gauci, Davide Mattiolo, Giuseppe Mazzuoccolo, Federico Romaniello, Christian Rubio-Montiel, Tommaso Traetta, 2025, original scientific article Abstract: A proper total colouring of a graph G is called harmonious if it has the further property that when replacing each unordered pair of incident vertices and edgeswith their colours, then no pair of colours appears twice. The smallest number of colours for it to exist is called the harmonious total chromatic number of G, denoted by h_t(G). Here, we give a general upper bound for h_t(G) in terms of the order n of G. Our two main results are obvious consequences of the computation of the harmonious total chromatic number of the complete graph Kn and of the complete multigraph λK_n, where λ is the number of edges joining each pair of vertices of Kn. In particular, Araujo-Pardo et al. have recently shown that 3/2 n ≤ h_t(K_n)≤ 5/3 n + θ(1). In this paper, we prove that h_t(K_n) = ⌈3/2 n⌉ except for h_t(K₁) = 1 and h_t(K₄) = 7; therefore, h_t(G)≤ ⌈3/2 n⌉, for every graph G on n > 4 vertices. Finally, we extend such a result to the harmonious total chromatic number of the complete multigraph λKn and as a consequence show that h_t(G) ≤ (λ-1)(2⌈n/2⌉-1)+⌈3n/2⌉ for n > 4, where G is a multigraph such that λ is the maximum number of edges between any two vertices.
Keywords: total colouring, harmonious colouring, complete graphs, complete multigraphs, Levi graph
Published in RUP: 03.11.2025; Views: 364; Downloads: 12
 Full text (387,22 KB) |
2. Primitive, edge-short, isometric, and pantochordal cyclesGover E. C. Guzman, Marcos E. González Laffitte, André Fujita, Peter F. Stadler, 2025, original scientific article Abstract: A cycle in a graph G is said to be primitive from its vertex x if at least one of its edges does not belong to any shorter cycle that passes through x. This type of cycle and an associated notion of extended neighborhoods play a key role in message-passing algorithms that compute spectral properties of graphs with short loops. Here, we investigate such primitive cycles and graphs without long primitive cycles in a more traditional graph-theoretic framework. We show that a cycle is primitive from all its vertices if and only if it is isometric. We call a cycle fully redundant cycles if it is not primitive from any of its vertices and show that fully redundant cycles, in particular, are not edge short, i.e., they cannot be represented as the edge-disjoint union of a single edge and two shortest paths in G. The families Rk and Lk of graphs with all cycles of length at least k + 1 being fully redundant and not edge-short, respectively, coincide for k = 3 and k = 4. In these graphs, all cycles of length at least k + 1 are pantochordal, i.e., each of their vertices is incident with a chord. None of these results generalizes to k ≥ 5. Moreover, R₃ = L₃ turn out to be the block graphs, and R₄ = L₄ are the graphs with complete multi-partite blocks. The cographs, finally, are shown to form a proper subset of R₅.
Keywords: edge-short cycle, chord, block-graph, complete multipartite graph, wheel graphs, cographs, geodesic cycles, Hamiltonian cycles
Published in RUP: 03.11.2025; Views: 269; Downloads: 1
Full text (478,50 KB) |
3. Colour-permuting automorphisms of complete Cayley graphsShirin Alimirzaei, Dave Witte Morris, 2025, original scientific article Abstract: Let G be a (finite or infinite) group, and let KG = Cay(G; G \ {1}) be the complete graph with vertex set G, considered as a Cayley graph of G. Being a Cayley graph, it has a natural edge-colouring by sets of the form {s, s-1} for s in G. We prove that every colour-permuting automorphism of KG is an affine map, unless G is isomoprhic to the direct product of Q8 and B, where Q8 is the quaternion group of order 8, and B is an abelian group, such that b2 is trivial for all b in B.
We also prove (without any restriction on G) that every colour-permuting automorphism of KG is the composition of a group automorphism and a colour-preserving graph automorphism. This was conjectured by D. P. Byrne, M. J. Donner, and T. Q. Sibley in 2013.
Keywords: Cayley graph, automorphism, colour-permuting, complete graphs
Published in RUP: 03.11.2025; Views: 260; Downloads: 1
Full text (453,60 KB) |
4. |
5. Set graphs. II. Complexity of set graph recognition and similar problemsMartin Milanič, Romeo Rizzi, Alexandru I. Tomescu, 2014, original scientific article Keywords: acyclic orientation, extensionality, set graphs, NP-complete problem, #P-complete problem, hyper-extensional digraphs, separating code, open-out-separating code
Published in RUP: 03.04.2017; Views: 3735; Downloads: 136
 Link to full text |
