Upper total domination in claw-free cubic graphs

DOI10.1007/S00373-022-02581-0MaRDI QIDQ2084795zbMATH OpenOpenAlexFDO

Authors Ammar Babikir, Michael A. Henning

Publication date 13 October 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-022-02581-0

zbMATH Keywords

claw-free cubic graph total domination upper total domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

Let \(G = (V, E)\) be a simple graph of order \(n\). A total dominating set of \(G\) is a subset \(D\) of \(V\) such that every vertex of \(V\) is adjacent to some vertices of \(D\). The total domination number of \(G\) is equal to the minimum cardinality of a total dominating set in \(G\) and is denoted by \(\gamma_t(G)\). The upper total domination number, \(\Gamma_t(G)\), of \(G\) is the maximum cardinality of a minimal total dominating set of \(G\). A claw-free graph is a graph that does not contain a claw \(K_{1,3}\) as an induced subgraph. Let \(G\) be a connected, claw-free, cubic graph of order \(n\). Since \(\gamma_t(G)\geq \frac{n}{\Delta(G)}\) for every isolate-free graph, we observe that \(\gamma_t(G)\geq \frac{1}{3}n\), and this bound is sharp. Recently, it is proved that if we exclude four graphs, then \(\gamma_t(G)\leq \frac{3}{7}n\). In this paper, the authors show that \(\frac{4}{9}n \leq \Gamma_t(G)\leq \frac{3}{5}n\).

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Upper total domination in claw-free cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084795)