Decompositions of complete graphs into isomorphic cubes

It is shown that, for any positive integer d, the d-dimensional cube W_d has an α-valuation. This implies that any complete graph K_2cn+1 (where n = d2^d-1 is the number of edges of W_d and c is an arbitrary positive integer) can be decomposed into edge disjoint copies of W_d.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

Decompositions of complete graphs into isomorphic bipartite subgraphs

Let |E(G)|= andf, a 1-1 mapping ofV(G) into {0,1,...,}. Thenf is called a -valuation ofG if the induced function given by , for alluvE(G) is 1-1. A -valuationf is called an -valuation ofG if there exists a nonnegative number such that for everyuvE(G) withf(u)<f(v),f(u)<f(v). Let denote the graph of then-dimensionalG-cube. ForG=K _{3, 3},K _{4, 4}, andP _k ,it is shown that for any positive integern, then-dimensionalG-cube has an -valuation. This gives rise to decompositions of some complete graphs into certain bipartite graphs.     

Decompositions of complete graphs into regular bichromatic factors

The proof of the following theorem is given: A complete graph with n vertices can be decomposed into r regular bichromatic factors if and only if n is even and greater than 4 and there exists a natural number k with the properties that k ≤ r and 2^{k ? 1} < n ≤ 2^k.     

Packing trees into planar graphs

In this study, we provide methods for drawing a tree with n vertices on a convex polygon, without crossings and using the minimum number of edges of the polygon. We apply the results to obtain planar packings of two trees in some specific cases. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 172–181, 2002     

Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n ≥ 1, let G_n denote the complete graph of order n, and for all even integers n ≥ 2 let G_n denote the complete graph of order n with the edges of a 1‐factor removed. It is shown that for all non‐negative integers h and t and all positive integers n, G_n can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G_n. © 2004 Wiley Periodicals, Inc.     

Decompositions of highly connected graphs into paths of length 3

We prove that a 171‐edge‐connected graph has an edge‐decomposition into paths of length 3 if and only its size is divisible by 3. It is a long‐standing problem whether 2‐edge‐connectedness is sufficient for planar triangle‐free graphs, and whether 3‐edge‐connectedness suffices for graphs in general. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 286–292, 2008     

Decompositions of edge-coloured infinite complete graphs into monochromatic paths II

We prove that given an edge colouring of an infinite complete graph with finitely many colours, one can partition the vertices of the graph into disjoint monochromatic paths of different colours. This answers a question of R. Rado from 1978.     

Decomposition of some planar graphs into trees

We prove that each simple planar graph G whose all faces are quadrilaterals can be decomposed into two disjoint trees T_r and T_b such that V(T_r) = V(G − u) and V(T_b) = V(G − v) for any two non-adjacent vertices u and v of G.     

Decompositions of complete multipartite graphs

This paper answers a recent question of Dobson and Maruši? by partitioning the edge set of a complete bipartite graph into two parts, both of which are edge sets of arc-transitive graphs, one primitive and the other imprimitive. The first member of the infinite family is the one constructed by Dobson and Maruši?.     

Decompositions for edge-coloring join graphs and cobipartite graphs

An edge-coloring is an association of colors to the edges of a graph, in such a way that no pair of adjacent edges receive the same color. A graph G is Class 1 if it is edge-colorable with a number of colors equal to its maximum degree Δ(G). To determine whether a graph G is Class 1 is NP-complete [I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718-720]. First, we propose edge-decompositions of a graph G with the goal of edge-coloring G with Δ(G) colors. Second, we apply these decompositions for identifying new subsets of Class 1 join graphs and cobipartite graphs. Third, the proposed technique is applied for proving that the chromatic index of a graph is equal to the chromatic index of its semi-core, the subgraph induced by the maximum degree vertices and their neighbors. Finally, we apply these decomposition tools to a classical result [A.J.W. Hilton, Z. Cheng, The chromatic index of a graph whose core has maximum degree 2, Discrete Math. 101 (1992) 135-147] that relates the chromatic index of a graph to its core, the subgraph induced by the maximum degree vertices.     

Decompositions of complete bipartite and tripartite graphs into selfcomplementary factors with finite diameters

We completely determine the spectrum of the complete bipartite and tripartite graphs that are decomposable into two isomorphic factors with a finite diameter.1991 Mathematics Subject Classification. 05C70     

Decompositions of homology manifolds and their graphs

The graph of everyd-dimensional convex polytope isd-connected and contains a refinement of the complete graph ond+1 vertices. These two theorems are generalized to pseudomanifolds and to some very general decompositions of homology manifolds. Research supported by N.S.F. Grant #MPS-74-04830/1.     

Decompositions of graphs via generalized graceful labelings

In [Pasotti, A., On d-graceful labelings, to appear on Ars Combin] a d-divisible α-labeling is defined as a generalization of the classical one of Rosa (see [Rosa, A., On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349–355]) and, similarly to the classical case, it is proved that there exists a link between d-divisible α-labelings of a graph Γ and cyclic Γ-decompositions. In [Benini, A., and Pasotti, A., Decompositions of complete multipartite graphs via generalized graceful labelings, submitted. (arXiv:1210.4370)] we have dealt with the existence of d-divisible α-labelings of caterpillars and certain classes of cycles and hairy cycles and the resulting possible decompositions.     

Independent trees in graphs

IfG is a finite undirected graph ands is a vertex ofG, then two spanning treesT ₁ andT ₂ inG are calleds — independent if for each vertexx inG the paths fromx tos inT ₁ andT ₂ are openly disjoint. It is known that the following statement is true fork3: IfG isk-connected, then there arek pairwises — independent spanning, trees inG. As a main result we show that this statement is also true fork=4 if we restrict ourselves to planar graphs. Moreover we consider similar statements for weaklys — independent spanning trees (i.e., the tree paths from a vertex tos are edge disjoint) and for directed graphs.