Displaying similar documents to “Packing independent sets and transversals”

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

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

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

Placing bipartite graphs of small size II

Beata Orchel (1996)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.

A note on uniquely embeddable graphs

Mariusz Woźniak (1998)

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 embedding G into its complement [G̅]. In this note, we consider a problem concerning the uniqueness of such an embedding.

Packing of (0, 1)-matrices

Stéphane Vialette (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

The MATRIX PACKING DOWN problem asks to find a row permutation of a given -matrix in such a way that the total sum of the first non-zero column indexes is maximized. We study the computational complexity of this problem. We prove that the MATRIX PACKING DOWN problem is -complete even when restricted to zero trace symmetric -matrices or to -matrices with at most two 's per column. Also, as intermediate results, we introduce several new simple graph layout problems which are proved...

On cyclically embeddable graphs

Mariusz Woźniak (1999)

Discussiones Mathematicae Graph Theory

Similarity:

An embedding of a simple graph G into its complement G̅ is a permutation σ on V(G) such that if an edge xy belongs to E(G), then σ(x)σ(y) does not belong to E(G). In this note we consider some families of embeddable graphs such that the corresponding permutation is cyclic.

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

On cyclically embeddable (n,n)-graphs

Agnieszka Görlich, Monika Pilśniak, Mariusz Woźniak (2003)

Discussiones Mathematicae Graph Theory

Similarity:

An embedding of a simple graph G into its complement G̅ is a permutation σ on V(G) such that if an edge xy belongs to E(G), then σ(x)σ(y) does not belong to E(G). In this note we consider the embeddable (n,n)-graphs. We prove that with few exceptions the corresponding permutation may be chosen as cyclic one.

New Bounds on the Signed Total Domination Number of Graphs

Seyyed Mehdi Hosseini Moghaddam, Doost Ali Mojdeh, Babak Samadi, Lutz Volkmann (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we study the signed total domination number in graphs and present new sharp lower and upper bounds for this parameter. For example by making use of the classic theorem of Turán [8], we present a sharp lower bound on Kr+1-free graphs for r ≥ 2. Applying the concept of total limited packing we bound the signed total domination number of G with δ(G) ≥ 3 from above by [...] . Also, we prove that γst(T) ≤ n − 2(s − s′) for any tree T of order n, with s support vertices and...

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

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

Some results on total domination in direct products of graphs

Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Spacapan (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.