TY - GEN
T1 - Face-Hitting Dominating Sets in Planar Graphs
AU - Francis, P.
AU - Illickan, Abraham M.
AU - Jose, Lijo M.
AU - Rajendraprasad, Deepak
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
PY - 2025
Y1 - 2025
N2 - A dominating set of a graph G is a subset S of its vertices such that each vertex of G not in S has a neighbor in S. A face-hitting set of a plane graph G is a set T of vertices in G such that every face of G contains at least one vertex of T. We show that the vertex-set of every plane (multi-)graph without isolated vertices, self-loops or 2-faces can be partitioned into two disjoint sets so that both the sets are dominating and face-hitting. We also show that all the three assumptions above are necessary for the conclusion. As a corollary, we show that every n-vertex simple plane triangulation has a dominating set of size at most (1-α)n/2, where αn is the maximum size of an independent set in the triangulation. Matheson and Tarjan [European J. Combin., 1996] conjectured that every plane triangulation with a sufficiently large number of vertices n has a dominating set of size at most n/4. Currently, the best known general bound for this is by Christiansen, Rotenberg and Rutschmann [6] [SODA, 2024] who showed that every plane triangulation on n>10 vertices has a dominating set of size at most 2n/7. Our corollary improves their bound for n-vertex plane triangulations which contain a maximal independent set of size either less than 2n/7 or more than 3n/7.
AB - A dominating set of a graph G is a subset S of its vertices such that each vertex of G not in S has a neighbor in S. A face-hitting set of a plane graph G is a set T of vertices in G such that every face of G contains at least one vertex of T. We show that the vertex-set of every plane (multi-)graph without isolated vertices, self-loops or 2-faces can be partitioned into two disjoint sets so that both the sets are dominating and face-hitting. We also show that all the three assumptions above are necessary for the conclusion. As a corollary, we show that every n-vertex simple plane triangulation has a dominating set of size at most (1-α)n/2, where αn is the maximum size of an independent set in the triangulation. Matheson and Tarjan [European J. Combin., 1996] conjectured that every plane triangulation with a sufficiently large number of vertices n has a dominating set of size at most n/4. Currently, the best known general bound for this is by Christiansen, Rotenberg and Rutschmann [6] [SODA, 2024] who showed that every plane triangulation on n>10 vertices has a dominating set of size at most 2n/7. Our corollary improves their bound for n-vertex plane triangulations which contain a maximal independent set of size either less than 2n/7 or more than 3n/7.
UR - https://www.scopus.com/pages/publications/85218452775
UR - https://www.scopus.com/pages/publications/85218452775#tab=citedBy
U2 - 10.1007/978-3-031-75409-8_15
DO - 10.1007/978-3-031-75409-8_15
M3 - Conference contribution
AN - SCOPUS:85218452775
SN - 9783031754081
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 211
EP - 219
BT - Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers
A2 - Kráľ, Daniel
A2 - Milanič, Martin
PB - Springer Science and Business Media Deutschland GmbH
T2 - 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024
Y2 - 19 June 2024 through 21 June 2024
ER -