✦ LIBER ✦

Signed Domination in Regular Graphs and Set-Systems

✍ Scribed by Zoltán Füredi; Dhruv Mubayi

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 188 KB
Volume: 76
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1999.1905

No coin nor oath required. For personal study only.

✦ Synopsis

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 number of &1's by more than (4 -log rÂr+1Âr) n. For large r this greatly improves earlier results and is almost optimal, since starting with an Hadamard matrix of order r, a bipartite r-regular graph is constructed on 4r vertices with signed domination number at least (1Â2) -r&O(1). The determination of lim n Ä # s (G)Ân remains open and is conjectured to be 3(1Â-r).

📜 SIMILAR VOLUMES

Set domination in graphs

✍ E. Sampathkumar; L. Pushpa Latha 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ = (__V, E__) be a connected graph. A set __D__ ⊂ __V__ is a __set‐dominating set__ (sd‐set) if for every set __T__ ⊂ __V__ − __D__, there exists a nonempty set __S__ ⊂ __D__ such that the subgraph 〈__S__ ∪ __T__〉 induced by __S__ ∪ __T__ is connected. The set‐domination number

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.

Independent Dominating Sets and a Second

Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs

✍ Carsten Thomassen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 241 KB

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r 3) has a second Hamiltonian cycle. We shall verify this for r 300.

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

Maximum acyclic and fragmented sets in r

Maximum acyclic and fragmented sets in regular graphs

✍ Penny Haxell; Oleg Pikhurko; Andrew Thomason 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## Abstract We show that a typical __d__‐regular graph __G__ of order __n__ does not contain an induced forest with around ${2 {\rm In} d \over d}$ vertices, when __n__ ≫ __d__ ≫ 1, this bound being best possible because of a result of Frieze and Łuczak [6]. We then deduce an affirmative answer to

Uniqueness of maximal dominating cycles

Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs

✍ Herbert Fleischner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB 👁 2 views

## Abstract We construct 3‐regular (cubic) graphs __G__ that have a dominating cycle __C__ such that no other cycle __C__~1~ of __G__ satisfies __V(C)__ ⊆ __V__(__C__~1~). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these const