Page 1 Next

Displaying 1 – 20 of 373

Showing per page

Packing four copies of a tree into a complete bipartite graph

Liqun Pu, Yuan Tang, Xiaoli Gao (2022)

Czechoslovak Mathematical Journal

In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree T of order n and each integer k 2 , there is a k -packing of T in a complete bipartite graph B n + k - 1 whose order is n + k - 1 . We prove the conjecture is true for k = 4 .

Packing of nonuniform hypergraphs - product and sum of sizes conditions

Paweł Naroski (2009)

Discussiones Mathematicae Graph Theory

Hypergraphs H , . . . , H N 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.

Packing of three copies of a digraph into the transitive tournament

Monika Pilśniak (2004)

Discussiones Mathematicae Graph Theory

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.

Packing Parameters in Graphs

I. Sahul Hamid, S. Saravanakumar (2015)

Discussiones Mathematicae Graph Theory

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.

Packing the Hypercube

David Offner (2014)

Discussiones Mathematicae Graph Theory

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.

Packing Trees Into n-Chromatic Graphs

András Gyárfás (2014)

Discussiones Mathematicae Graph Theory

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.

Currently displaying 1 – 20 of 373

Page 1 Next