Upper distance-two domination

<jats:p>Let \(G = (V, E)\) be a graph with vertex set \(V\) and edge set \(E\). A set \(S \subset V\) is a \(2\)-packing in \(G\) if for any two vertices \(u,v \in S\), the distance between them satisfies \(d(u,v) \gt 2\). The upper \(2\)-packing number \(P_2(G)\) is the maximum cardinality of a \(2\)-packing in \(G\). A set \(S \subset V\) is a dominating set for \(G\) if every vertex in \(V - S\) is adjacent to at least one vertex in \(S\). The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set in \(G\). A set \(S \subset V\) is a distance-\(2\) dominating set if for every vertex \(v \in V - S\) there exists a vertex \(u \in S\) such that \(d(u,v) \leq 2\). The upper distance-\(2\) domination number \(\Gamma_{\leq 2}(G)\) is the maximum cardinality of a minimal distance-\(2\) dominating set in \(G\). In this paper we establish two families of graphs \(G\) for which \(P_2(G) = \gamma(G) = \Gamma_{\leq 2}(G)\), which extend several well-known equalities of the form \(P_2(G) = \gamma(G)\).</jats:p>

Authors

Publication Details

Journal
Opuscula Mathematica
Published
2025-01-01
DOI
https://doi.org/10.7494/opmath.2025.45.3.339
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Upper distance-two domination

Jason T. Hedetniemi, Thomas M. Lewis, Stephen T. Hedetniemi
Opuscula Mathematica
Advanced Graph Theory Research
article

Upper distance-two domination

Jason T. Hedetniemi, Thomas M. Lewis, Stephen T. Hedetniemi
article en

Abstract

<jats:p>Let \(G = (V, E)\) be a graph with vertex set \(V\) and edge set \(E\). A set \(S \subset V\) is a \(2\)-packing in \(G\) if for any two vertices \(u,v \in S\), the distance between them satisfies \(d(u,v) \gt 2\). The upper \(2\)-packing number \(P_2(G)\) is the maximum cardinality of a \(2\)-packing in \(G\). A set \(S \subset V\) is a dominating set for \(G\) if every vertex in \(V - S\) is adjacent to at least one vertex in \(S\). The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set in \(G\). A set \(S \subset V\) is a distance-\(2\) dominating set if for every vertex \(v \in V - S\) there exists a vertex \(u \in S\) such that \(d(u,v) \leq 2\). The upper distance-\(2\) domination number \(\Gamma_{\leq 2}(G)\) is the maximum cardinality of a minimal distance-\(2\) dominating set in \(G\). In this paper we establish two families of graphs \(G\) for which \(P_2(G) = \gamma(G) = \Gamma_{\leq 2}(G)\), which extend several well-known equalities of the form \(P_2(G) = \gamma(G)\).</jats:p>

Opuscula Mathematica
Openalex Percentile: Top 87%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Upper distance-two domination — Jason T. Hedetniemi, Thomas M. Lewis, et al. · Opuscula Mathematica (2025) | TGRS Research Map | TGRS