Graph equations for line graphs,total graphs,middle graphs and quasi-total graphs

Let G be a graph with vertex-set V(G) and edge-set X(G). Let L(G) and T(G) denote the line graph and total graph of G. The middle graph M(G) of G is an intersection graph Ω(F) on the vertex-set V(G) of any graph G. Let F = V′(G) ∪ X(G) where V′(G) indicates the family of all one-point subsets of the set V(G), then $\text{M(G) = Ω(F)}$.The quasi-total graph P(G) of G is a graph with vertex-set V(G)∪X(G) and two vertices are adjacent if and only if they correspond to two non-adjacent vertices of G or to two adjacent edges of G or to a vertex and an edge incident to it in G.In this paper we solve graph equations $\text{L(G) ? P(H);}\text{L(G)}\text{? P(H); P(G) ? T(H);}\text{P(G)}\text{? T(H); M(G) ? P(H);}\text{M(G)}\text{? P(H)}$.     

Hamiltonian decompositions of complete graphs

It is well known that K_{2n + 1} can be decomposed into n edge-disjoint Hamilton cycles. A novel method for constructing Hamiltonian decompositions of K_{2n + 1} is given and a procedure for obtaining all Hamiltonian decompositions of of K_{2n + 1} is outlined. This method is applied to find a necessary and sufficient condition for a decomposition of the edge set of K_r (r ≤ 2n) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of K_{2n + 1} so that each of the classes forms part of a Hamilton cycle.     

Isomorphic decomposition of complete graphs into linear forests

The well-known theorem of Kirkman states that every complete graph K_2n of order 2n is 1-factorable or, equivalently, is nK₂-decomposable. This result is generalized to any linear forest of size n without isolated vertices.     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.     

Nomadic decompositions of bidirected complete graphs

We use to denote the bidirected complete graph on n vertices. A nomadic Hamiltonian decomposition of is a Hamiltonian decomposition, with the additional property that “nomads” walk along the Hamiltonian cycles (moving one vertex per time step) without colliding. A nomadic near-Hamiltonian decomposition is defined similarly, except that the cycles in the decomposition have length n-1, rather than length n. Bondy asked whether these decompositions of exist for all n. We show that admits a nomadic near-Hamiltonian decomposition when .     

Hamilton decompositions of some line graphs

The main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if G is a bipartite (2k + 1)-regular graph that is Hamilton decomposable, then the line graph, L(G), of G is also Hamilton decomposable. A similar result is obtained for 5-regular graphs, thus providing further evidence to support Bermond's conjecture. © 1995 John Wiley & Sons, Inc.     

Hamiltonian decompositions of complete regular s-partite graphs

In this paper we give a procedure by which Hamiltonian decompositions of the s-partite graph K_n,n,…,n, where (s − 1)n is even, can be constructed. For 2t⩽s, 1⩽a₁⩽…⩽a_t⩽n, we find conditions which are necessary and sufficient for a decomposition of the edge-set of K_a1a2…,a_t into (s − 1)n/2 classes, each class consisting of disjoint paths, to be extendible to a Hamiltonian decomposition of the complete s-partite graph K_rmn,n,…,n so that each of the classes forms part of a Hamiltonian cycle.     

More on decompositions of edge-colored complete graphs

Let G be a family of graphs whose edges are colored with elements from a set R of r colors. We assume no two vertices of G are joined by more than one edge of color i for any i∈R, for each G∈G. will denote the complete graph with r edges joining any pair of distinct vertices, one of each of the r colors. We describe necessary and asymptotically sufficient conditions on n for the existence of a family D of subgraphs of , each of which is an isomorphic copy of some graph in G, so that each edge of appears in exactly one of the subgraphs in D.     

On cyclic decompositions of the complete graph into the 2-regular graphs

The symbol C(m₁ ⁿ ₁m₂ ⁿ ₂...m_s ⁿ _s) denotes a 2-regular graph consisting ofn _i cycles of lengthm _i , i=1, 2,…,s. In this paper, we give some construction methods of cyclic(K _v ,G)-designs, and prove that there exists a cyclic(K _v , G)-design whenG=C((4m ₁) ⁿ ₁(4m ₂) ⁿ ₂...(4m _s ) ⁿ _s andv ≡ 1 (mod 2¦G¦).     

Hamilton cycle decompositions of the tensor products of complete bipartite graphs and complete multipartite graphs

In this paper, it is shown that the tensor product of the complete bipartite graph, K_r,r,r≥2, and the regular complete multipartite graph, , is Hamilton cycle decomposable.     

Resolvable gregarious cycle decompositions of complete equipartite graphs

The complete multipartite graph K_n(m) with n parts of size m is shown to have a decomposition into n-cycles in such a way that each cycle meets each part of K_n(m); that is, each cycle is said to be gregarious. Furthermore, gregarious decompositions are given which are also resolvable.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

The binding number of line graphs and total graphs

D.R. Woodall [7] introduced the concept of the binding number of a graphG, bind (G), and proved that bind(G)≦(|V(G)|−1)/(|V(G)|−ρ(G)). In this paper, some properties of a graph with bind(G)=(|V(G)|−1)/(|V(G)|−ρ(G)) are given, and the binding number of some line graphs and total graphs are determined.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.