We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
OUTER CONNECTED DOMINATION IN MAXIMAL OUTERPLANAR GRAPHS AND BEYOND.
- Authors
WEI YANG; BAOYINDURENG WU
- Abstract
A set S of vertices in a graph G is an outer connected dominating set of G if every vertex in V\S is adjacent to a vertex in S and the subgraph induced by V\S is connected. The outer connected domination number of G, denoted by γc(G), is the minimum cardinality of an outer connected dominating set of G. Zhuang [Domination and outer connected domination in maximal outerplanar graphs, Graphs Combin. 37 (2021) 2679-2696] recently proved that γc(G) ≤ ⌈n+k/4 ⌉ for any maximal outerplanar graph G of order n ≥ 3 with k vertices of degree 2 and posed a conjecture which states that G is a striped maximal outerplanar graph with γc(G) = ⌈n+2/4 ⌉ if and only if G ∈ A, where A consists of six special families of striped outerplanar graphs. We disprove the conjecture. Moreover, we show that the conjecture become valid under some additional property to the striped maximal outerplanar graphs. In addition, we extend the above theorem of Zhuang to all maximal K2,3-minor free graphs without K4 and all K4-minor free graphs. Keywords: maximal outerplanar graphs, outer connected domination, striped maximal outerplanar graphs.
- Subjects
DOMINATING set; LOGICAL prediction; STRIPES
- Publication
Discussiones Mathematicae: Graph Theory, 2024, Vol 44, Issue 2, p575
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.2462