Towards the conjecture on domination versus edge domination in graphs
The graphs considered are finite, simple, and undirected graphs. Let the vertex set and edge set of the graph be denoted by \(V(G)\) and \(E(G)\) respectively. A dominating set of \(G\) is a subset \(D \subseteq V\) such that every vertex of \(V(G)\setminus D\) is adjacent to at least one vertex of \(D\). The minimum cardinality of a dominating set of a graph \(G\) is called the domination number of graph \(G\) and is denoted by \(\gamma(G)\). An edge dominating set of \(G\) is a subset \(F \subseteq E\) such that every edge in \(E(G)\setminus F\) is adjacent to at least one edge of \(F\). The minimum cardinality of an edge dominating set of a graph \(G\) is called the edge domination number of \(G\) and is denoted by \(\gamma_e(G)\). \textit{J. Baste} et al. [Discrete Appl. Math. 285, 343--349 (2020; Zbl 1466.05155)] conjectured that if \(G\) is a \(\Delta\)-regular graph with \(\Delta \geq 1\), then \(\gamma(G) \leq \gamma_e(G)\). \textit{Y. Civan} et al. [ibid. 337, 171--172 (2023; Zbl 1520.05072)] proved the result to be true for a claw-free graph with minimum degree of at least two. A fork is a graph that is obtained by attaching a pendant vertex to one of the vertex of a path \(P_4\) having degree two. A graph is fork-free if the graph does not contain any induced subgraph that is isomorphic to fork. In the paper under review, the authors prove the conjecture to be true for fork-free graphs with minimum degree of at least two. Moreover, they also prove the conjecture to be valid for \(P_4\)-free graph with minimum degree at least one.
- Mathematical theories of traffic flow
- Modeling, estimation, and their applications for distributed parameter systems
- scientific article; zbMATH DE number 5055270
- Lefschetz's principle
- Superheating behavior in a breakdown reactor
- scientific article; zbMATH DE number 3188569
- scientific article; zbMATH DE number 3133698
- Pointwise Bounds for Solutions of Semilinear Parabolic Equations
This page was built for publication: Towards the conjecture on domination versus edge domination in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6186325)
