On the complexity of partitioning graphs into connected subgraphs

This paper is mainly concerned with the computational complexity of determining whether or not the vertices of a graph can be partitioned into equal sized subsets so that each subset induces a particular type of graph. Many of the NP-completeness results are for planar graphs. These are proved using a planar version of 3-dimensional matching.     

Highly connected multicoloured subgraphs of multicoloured graphs

Suppose the edges of the complete graph on n vertices, E(K_n), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4, that if r=2s+1 then the answer lies between and , and that phase transitions occur at s=r/2 and . We shall also mention some of the more glaring open problems relating to this question.     

Contractible subgraphs in k‐connected graphs

For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007     

On the number of certain subgraphs contained in graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheres≧r. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess ₁≧s ₂≧…≧s _r>r, provided (s ₁−s _r)²<s ₁+s _r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l ^k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars.     

On the number of subgraphs of prescribed type of graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For a graphH=〈V(H),E(H)〉 and forS ⊂V(H) defineN(S)={x ∈V(H):xy ∈E(H) for somey ∈S}. Define alsoδ(H)= max {|S| − |N(S)|:S ⊂V(H)},γ(H)=1/2(|V(H)|+δ(H)). For two graphsG, H letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also forl>0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We investigate the asymptotic behaviour ofN(l, H) for fixedH asl tends to infinity. The main results are:Theorem A. For every graph H there are positive constants c ₁, c₂ such that {fx116-1}. Theorem B. If δ(H)=0then {fx116-2},where |AutH|is the number of automorphisms of H. (It turns out thatδ(H)=0 iffH has a spanning subgraph which is a disjoint union of cycles and isolated edges.) This paper forms part of an M.Sc. Thesis written by the author under the supervision of Prof. M. A. Perles from the Hebrew University of Jerusalem.     

Partitioning a graph into monochromatic connected subgraphs

We show that every -edge-colored graph on vertices with minimum degree at least can be partitioned into two monochromatic connected subgraphs, provided is sufficiently large. This minimum degree condition is tight and the result proves a conjecture of Bal and DeBiasio. We also make progress on another conjecture of Bal and DeBiasio on covering graphs with large minimum degree with monochromatic components of distinct colors.     

Decomposition of bipartite graphs into special subgraphs

Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F₁,F₂,…,F_m is called an F-factorization of G orthogonal to H if F_i≅F and |E(F_i∩H)|=1 for each i=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K_4k,4k has a C₄-factorization orthogonal to H provided that H is a k-factor of K_4k,4k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r?k, K_kr²,kr² has a K_r,r-factorization orthogonal to H if H is a k-factor of K_kr²,kr²; (3) K_2d²,2d² has a C₄-factorization such that each edge of H belongs to a different C₄ if H is a subgraph of K_2d²,2d² with maximum degree Δ(H)?d.     

On the number of connected convex subgraphs of a connected acyclic digraph

A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.     

Hamiltonicity and forbidden subgraphs in 4‐connected graphs

Let T be the line graph of the unique tree F on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., T is a chain of three triangles. We show that every 4‐connected {T, K_1,3}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 262–272, 2005     

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.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

On spanning connected graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k^*-connected graphs.     

On path connected graphs

Given n and i, n > 2, 2 ≤ i ≤ n ? 1, the smallest size of an n-graph without endvertices is obtained, which ensures a path of length i between any two vertices of the graph.     

On planar intersection graphs with forbidden subgraphs

Let be a family of n compact connected sets in the plane, whose intersection graph has no complete bipartite subgraph with k vertices in each of its classes. Then has at most n times a polylogarithmic number of edges, where the exponent of the logarithmic factor depends on k. In the case where consists of convex sets, we improve this bound to O(n log n). If in addition k = 2, the bound can be further improved to O(n). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 205–214, 2008     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.