- Tytuł:
- Outer connected domination in maximal outerplanar graphs and beyond
- Autorzy:
-
Yang, Wei
Wu, Baoyindureng - Tematy:
-
maximal outerplanar graphs
outer connected domination
striped maximal outerplanar graphs - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/59896540.pdf Link otwiera się w nowym oknie
- Opis:
- A set $S$ of vertices in a graph $G$ is an outer connected dominating set of $G$ if every vertex in $V\setminus S$ is adjacent to a vertex in $S$ and the subgraph induced by $V\setminus S$ is connected. The outer connected domination number of $G$, denoted by $\tilde{\gamma_{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 \( \tilde{\gamma_{c}}(G)\leq \lfloor \tfrac{n+k}{4} \rfloor \) for any maximal outerplanar graph $G$ of order $n\geq 3$ with $k$ vertices of degree 2 and posed a conjecture which states that $G$ is a striped maximal outerplanar graph with \( \tilde{\gamma_{c}}(G)=\lfloor \tfrac{n+2}{4} \rfloor \) if and only if \( G\in \mathcal{A} \), where \( \mathcal{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 $K_{2,3}$-minor free graphs without $K_4$ and all $K_4$-minor free graphs.
- Dostawca treści:
- Biblioteka Nauki
Artykuł