✦ LIBER ✦

Signed domination in regular graphs

✍ Scribed by Odile Favaron

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 456 KB
Volume: 158
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(96)00026-x

No coin nor oath required. For personal study only.

✦ Synopsis

In answer to the open questions proposed by Henning and Slater, we give sharp upper bounds on the upper signed domination number of a regular graph and on the signed domination number of a connected cubic graph. Let G = (V, E) be a simple graph. For v E V, we denote by d(u) the degree of v in V, by N(v) the neighborhood of v, and by N[v]=N(u)U{v} its closed neighborhood.

📜 SIMILAR VOLUMES

Signed Domination in Regular Graphs and

Signed Domination in Regular Graphs and Set-Systems

✍ Zoltán Füredi; Dhruv Mubayi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Suppose G is a graph on n vertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of G with colors, +1 and &1, such that all closed neighborhoods contain more 1's than &1's, and all together the number of 1's does not exceed the numb

Independent domination in regular graphs

✍ Julie Haviland 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 387 KB

Let G be a simple graph of order n. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. Motivated by work of Cockayne et al. (1991) and Cockayne and Mynhardt (1989), we investigate the maximum value of the product of th

Minus domination in regular graphs

✍ Jean Dunbar; Stephen Hedetniemi; Michael A. Henning; Alice A. McRae 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 77 KB

Efficient minus and signed domination in

Efficient minus and signed domination in graphs

✍ Chin Lung Lu; Sheng-Lung Peng; Chuan Yi Tang 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 399 KB

An e cient minus (respectively, signed) dominating function of a graph G = (V; E) is a function f : The e cient minus (respectively, signed) domination problem is to ÿnd an e cient minus (respectively, signed) dominating function of G. In this paper, we show that the e cient minus (respectively, si

Regular matroid decomposition via signed

Regular matroid decomposition via signed graphs

✍ Jim Geelen; Bert Gerards 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

The key to Seymour's Regular Matroid Decomposition Theorem is his result that each 3-connected regular matroid with no R 10or R 12 -minor is graphic or cographic. We present a proof of this in terms of signed graphs.

Dominating cycles in regular 3-connected

Dominating cycles in regular 3-connected graphs

✍ Bill Jackson; Hao Li; Yongjin Zhu 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 744 KB

Jackson, B., H. Li and Y. Zhu, Dominating cycles in regular 3-connected graphs, Discrete Mathematics 102 (1992) 163-176. Let G be a 3-connected, k-regular graph on at most 4k vertices. We show that, for k > 63, every longest cycle of G is a dominating cycle. We conjecture that G is in fact hamilton