- Tytuł:
- On Independent Domination in Planar Cubic Graphs
- Autorzy:
-
Abrishami, Gholamreza
Henning, Michael A.
Rahbarnia, Freydoon - Powiązania:
- https://bibliotekanauki.pl/articles/31343229.pdf
- Data publikacji:
- 2019-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
independent domination number
domination number
cubic graphs - Opis:
- A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i(G)$, of $G$ is the minimum cardinality of an independent dominating set. Goddard and Henning [Discrete Math. 313 (2013) 839–854] posed the conjecture that if \( G \not\in \{ K_{3,3}, C_5 \square K_2 \} \) is a connected, cubic graph on $n$ vertices, then $i(G) \le 3/8 n $, where $ C_5 \square K_2 $ is the 5-prism. As an application of known result, we observe that this conjecture is true when $G$ is 2-connected and planar, and we provide an infinite family of such graphs that achieve the bound. We conjecture that if $G$ is a bipartite, planar, cubic graph of order $n$, then $ i(G) \le 1/3 n $, and we provide an infinite family of such graphs that achieve this bound.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 841-853
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł