In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree of order and each integer , there is a -packing of in a complete bipartite graph whose order is . We prove the conjecture is true for .
Hypergraphs of order n are mutually packable if one can find their edge disjoint copies in the complete hypergraph of order n. We prove that two hypergraphs are mutually packable if the product of their sizes satisfies some upper bound. Moreover we show that an arbitrary set of the hypergraphs is mutually packable if the sum of their sizes is sufficiently small.
In this paper, we show that if the number of arcs in an oriented graph G (of order n) without directed cycles is sufficiently small (not greater than [2/3] n-1), then there exist arc disjoint embeddings of three copies of G into the transitive tournament TTₙ. It is the best possible bound.
In a graph G = (V,E), a non-empty set S ⊆ V is said to be an open packing set if no two vertices of S have a common neighbour in G. An open packing set which is not a proper subset of any open packing set is called a maximal open packing set. The minimum and maximum cardinalities of a maximal open packing set are respectively called the lower open packing number and the open packing number and are denoted by ρoL and ρo. In this paper, we present some bounds on these parameters.
Let G be a graph that is a subgraph of some n-dimensional hypercube Qn. For sufficiently large n, Stout [20] proved that it is possible to pack vertex- disjoint copies of G in Qn so that any proportion r < 1 of the vertices of Qn are covered by the packing. We prove an analogous theorem for edge-disjoint packings: For sufficiently large n, it is possible to pack edge-disjoint copies of G in Qn so that any proportion r < 1 of the edges of Qn are covered by the packing.
We show that if a sequence of trees T1, T2, ..., Tn−1 can be packed into Kn then they can be also packed into any n-chromatic graph.
A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study. We focus on graphs that do not contain the net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (obtained by attaching...
In this note, we consider the partition of a graph into cycles containing a specified linear forest. Minimum degree and degree sum conditions are given, which are best possible.
Minimum disconnecting cuts of connected graphs provide fundamental information about the connectivity structure of the graph. Spectral methods are well-known as stable and efficient means of finding good solutions to the balanced minimum cut problem. In this paper we generalise the standard balanced bisection problem for static graphs to a new “dynamic balanced bisection problem”, in which the bisecting cut should be minimal when the vertex-labelled graph is subjected to a general sequence of vertex...
A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of...
For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n...