✦ LIBER ✦

On the domination number of cross products of graphs

✍ Scribed by Sylvain Gravier; Abdelkader Khelladi

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 195 KB
Volume: 145
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00091-a

No coin nor oath required. For personal study only.

✦ Synopsis

In this communication the domination number of the cross product of an elementary path with the complement of another path is exactly determined and some inequalities for general cases are deduced. The paper ends with a Vizing-like conjecture relating the domination number of the cross product of G and G' with the product of the corresponding ones.

📜 SIMILAR VOLUMES

On the domination of the products of gra

On the domination of the products of graphs II: Trees

✍ Michael S. Jacobson; Lael F. Kinch 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 377 KB

For a graph G, a subset of vertices D is a dominating set if for each vertex x not in D, x is adjacent to at least one vertex of D. The domination number, y(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H,

On the r-domination number of a graph

✍ Jerrold R. Griggs; Joan P. Hutchinson 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 468 KB

For r > 0, let the r-domination number of a graph, d,, be the size of a smallest set of vertices such that every vertex of the graph is within distance r of a vertex in that set. This paper contains proofs that every graph with a spanning tree with at least n/2 leaves has d, s n/(2r); this compares

On domination and independent domination

On domination and independent domination numbers of a graph

✍ Robert B. Allan; Renu Laskar 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 399 KB

For a graph G, the definitions of doknation number, denoted y(G), and independent domination number, denoted i(G), are given, and the following results are obtained: oorollrrg 1. For any graph G, y(L(G)) = i@(G)), where Z,(G) is the line graph of G. (This $xh!s t.lic rtsult ~(L(T))~i(L(T)), h w ere

Domination numbers of planar graphs

✍ MacGillivray, G.; Seyffarth, K. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 967 KB

The problem of determining the domination number of a graph is a well known NPhard problem, even when restricted to planar graphs. By adding a further restriction on the diameter of the graph, we prove that planar graphs with diameter two and three have bounded domination numbers. This implies that

On the crossing numbers of products of c

On the crossing numbers of products of cycles and graphs of order four

✍ Lowell W. Beineke; Richard D. Ringeisen 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 446 KB

The product of the independent dominatio

The product of the independent domination numbers of a graph and its complement

✍ E.J. Cockayne; O. Favaron; H. Li; G. MacGillivray 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 240 KB