Maximal reflexive cacti with four cycles: The approach via Smith graphs

Cacti, or treelike graphs, are graphs whose all cycles are mutually edge-disjoint. Graphs with the property are called reflexive graphs, where λ₂ is the second largest eigenvalue of the corresponding (0, 1)-adjacency matrix. The property is a hereditary one, i.e. all induced subgraphs of a reflexive graph are also reflexive. This is why we represent reflexive graphs through the maximal graphs within a given class (such as connected cacti with a fixed number of cycles). In previous work we have determined all maximal reflexive cacti with four cycles whose cycles do not form a bundle and pointed out the role of so-called pouring of Smith graphs in their construction. In this paper, besides pouring, we show several other patterns of the appearance of Smith trees in those constructions. These include splitting of a Smith tree, adding an edge to a Smith tree and then splitting of the resulting graph, identifying two vertices of a Smith tree and then splitting the resulting graph. Our results show that the presence of Smith trees is evident in all such maximal reflexive cacti with four cycles and that in most of them Smith graphs appear in the described way.     

Treelike comparability graphs

An undirected graph is a treelike comparability graph if it admits a transitive orientation such that its transitive reduction is a tree. We show that treelike comparability graphs are distance hereditary. Utilizing this property, we give a linear time recognition algorithm. We then characterize permutation graphs that are treelike. Finally, we consider the Partitioning into Bounded Cliques problem on special subgraphs of treelike permutation graphs.     

Edge-dominating cycles in graphs

A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157-183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams’ Theorem corresponds to the case of k=1 of this result.     

The swap graph of the finite soluble groups

A graph is reflexive if the second largest eigenvalue of its adjacency matrix is less than or equal to 2. In this paper, we characterize trees whose line graphs are reflexive. It turns out that these trees can be of arbitrary order—they can have either a unique vertex of arbitrary degree or pendant paths of arbitrary lengths, or both. Since the reflexive line graphs are Salem graphs, we also relate some of our results to the Salem (graph) numbers.     

On the Laplacian integral tricyclic graphs

A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. In this paper, we give an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1) and characterize a class of k-cyclic graphs whose algebraic connectivity is less than one. Using these results, we determine all the Laplacian integral tricyclic graphs. Furthermore, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.     

Star-Uniform Graphs

A star-factor of a graph is a spanning subgraph each of whose components is a star. A graph G is called star-uniform if all star-factors of G have the same number of components. Motivated by the minimum cost spanning tree and the optimal assignment problems, Hartnell and Rall posed an open problem to characterize all the star-uniform graphs. In this paper, we show that a graph G is star-uniform if and only if G has equal domination and matching number. From this point of view, the star-uniform graphs were characterized by Randerath and Volkmann. Unfortunately, their characterization is incomplete. By deploying Gallai–Edmonds Matching Structure Theorem, we give a clear and complete characterization of star-unform graphs.     

Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts

In 1998 Cavenagh [N.J. Cavenagh, Decompositions of complete tripartite graphs into k-cycles, Australas. J. Combin. 18 (1998) 193-200] gave necessary and sufficient conditions for the existence of an edge-disjoint decomposition of a complete equipartite graph with three parts, into cycles of some fixed length k. Here we extend this to paths, and show that such a complete equipartite graph with three partite sets of size m, has an edge-disjoint decomposition into paths of length k if and only if k divides 3m² and k<3m. Further, extending to five partite sets, we show that a complete equipartite graph with five partite sets of size m has an edge-disjoint decomposition into cycles (and also into paths) of length k with k?3 if and only if k divides 10m² and k?5m for cycles (or k<5m for paths).     

Edge-primitive Cayley graphs on abelian groups and dihedral groups

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups.     

Cycle Covers of Planar 2-Edge-Connected Graphs

A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.     

On the signless Laplacian index of cacti with a given number of pendant vertices

A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.     

Series parallel extensions of plane graphs to dual-eulerian graphs

A plane graph is dual-eulerian if it has an eulerian tour with the property that the same sequence of edges also forms an eulerian tour in the dual graph. Dual-eulerian graphs are of interest in the design of CMOS VLSI circuits.Every dual-eulerian plane graph also has an eulerian Petrie (left–right) tour thus we consider series-parallel extensions of plane graphs to graphs, which have eulerian Petrie tours. We reduce several special cases of extensions to the problem of finding hamiltonian cycles. In particular, a 2-connected plane graph G has a single series parallel extension to a graph with an eulerian Petrie tour if and only if its medial graph has a hamiltonian cycle.     

Upper Bound on the Diameter of a Domination Dot-Critical Graph

A vertex of a graph is called critical if its deletion decreases the domination number, and an edge is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In this paper, we show that if G is a connected dot-critical graph with domination number k??? 3 and diameter d and if G has no critical vertices, then d??? 2k?3.     

Multicolored parallelisms of Hamiltonian cycles

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we prove that a complete graph on 2m+1 vertices K_2m+1 can be properly edge-colored with 2m+1 colors in such a way that the edges of K_2m+1 can be partitioned into m multicolored Hamiltonian cycles.     

All 2-connected in-tournaments that are cycle complementary

An in-tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. A digraph D is cycle complementary if there exist two vertex-disjoint directed cycles spanning the vertex set of D. Let D be a 2-connected in-tournament of order at least 8. In this paper we show that D is not cycle complementary if and only if it is 2-regular and has odd order.     

Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface

A polyhedral embedding in a surface is one in which any two faces have boundaries that are either disjoint or simply connected. In a cubic (3-regular) graph this is equivalent to the dual being a simple graph. In 1968, Grünbaum conjectured that every cubic graph with a polyhedral embedding in an orientable surface is 3-edge-colorable. For the sphere, this is equivalent to the Four-Color Theorem, but we have disproved the conjecture in the general form. In this paper we extend this result and show that if we restrict our attention to a class of cubic graphs with a polyhedral embedding in an orientable surface, then the computational complexity of the 3-edge-coloring problem and its approximation does not improve.     

Graphs of given genus and arbitrarily large maximum genus

The maximum genus of a connected graph G is the maximum among the genera of all compact orientable 2-manifolds upon which G has 2-cell embeddings. In the theorems that follow the use of an edge-adding technique is combined with the well-known Edmonds' technique to produce the desired results. Planar graphs of arbitrarily large maximum genus are displayed in Theorem 1. Theorem 2 shows that the possibility for arbitrarily large difference between genus and maximum genus is not limited to planar graphs. In particular, we show that the wheel graph, the standard maximal planar graph, and the prism graph are upper embeddable. We then show that given m and n, there is a graph of genus n and maximum genus larger than mn.     

Sliding puzzles and rotating puzzles on graphs

Sliding puzzles on graphs are generalizations of the Fifteen Puzzle. Wilson has shown that the sliding puzzle on a 2-connected graph always generates all even permutations of the tiles on the vertices of the graph, unless the graph is isomorphic to a cycle or the graph θ₀ [R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combin. Theory Ser. B 16 (1974) 86–96]. In a rotating puzzle on a graph, tiles are allowed to be rotated on some of the cycles of the graph. It was shown by Scherphuis that all even permutations of the tiles are also obtainable for the rotating puzzle on a 2-edge-connected graph, except for a few cases. In this paper, Scherphuis’ Theorem is generalized to every connected graph, and Wilson’s Theorem is derived from the generalized Scherphuis’ Theorem, which will give a uniform treatise for these two families of puzzles and reveal the structural relation of the graphs of the two puzzles.     

Longest paths and cycles in bipartite oriented graphs

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2), on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense.