Displaying similar documents to “Labeled Embedding Of (n, n-2)-Graphs In Their Complements”

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....

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ₙ.

Packing Parameters in Graphs

I. Sahul Hamid, S. Saravanakumar (2015)

Discussiones Mathematicae Graph Theory

Similarity:

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 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...

Generalizations of the tree packing conjecture

Dániel Gerbner, Balázs Keszegh, Cory Palmer (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The Gyárfás tree packing conjecture asserts that any set of trees with 2,3,...,k vertices has an (edge-disjoint) packing into the complete graph on k vertices. Gyárfás and Lehel proved that the conjecture holds in some special cases. We address the problem of packing trees into k-chromatic graphs. In particular, we prove that if all but three of the trees are stars then they have a packing into any k-chromatic graph. We also consider several other generalizations of the conjecture. ...

Total domination in categorical products of graphs

Douglas F. Rall (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination...

Universal container for packing rectangles

Janusz Januszewski (2002)

Colloquium Mathematicae

Similarity:

The aim of the paper is to find a rectangle with the least area into which each sequence of rectangles of sides not greater than 1 with total area 1 can be packed.