Displaying similar documents to “The packing and covering of the complete graph. I: The forests of order five.”

A note on careful packing of a graph

M. Woźniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an edge-disjoint placement of two copies of G into Kₙ. We prove that with the same condition on size of G we have actually (with few exceptions) a careful packing of G, that is an edge-disjoint placement of two copies of G into Kₙ∖Cₙ.

A Note on Uniquely Embeddable Forests

Justyna Otfinowska, Mariusz Woźniak (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let F be a forest of order n. It is well known that if F 6= Sn, a star of order n, then there exists an embedding of F into its complement F. In this note we consider a problem concerning the uniqueness of such an embedding.

Labeled Embedding Of (n, n-2)-Graphs In Their Complements

M.-A. Tahraoui, E. Duchêne, H. Kheddouci (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Graph packing generally deals with unlabeled graphs. In [4], the authors have introduced a new variant of the graph packing problem, called the labeled packing of a graph. This problem has recently been studied on trees [M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled 2-packings of trees, Discrete Math. 338 (2015) 816-824] and cycles [E. Duchˆene, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109-126]. In this note, we...

Packing the Hypercube

David Offner (2014)

Discussiones Mathematicae Graph Theory

Similarity:

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 Coloring of Some Undirected and Oriented Coronae Graphs

Daouya Laïche, Isma Bouchemakh, Éric Sopena (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae...

Packing of graphs

Woźniak Mariusz

Similarity:

PrefaceThere are two basic reference texts on packing theory: the last chapter of Bollobás's book [6] (1978) and the 4th chapter of Yap's book [85] (1986). They still remain the main references to packing problems. However, many papers related to these problems have recently been published and the reason for writing this survey is to gather in a systematic form results scattered throughout the literature.I wish I could name all who deserve my thanks. I am particularly grateful to A....