Browsing by Author "Hedetniemi, Jason T."

Now showing 1 - 2 of 2

Access status: Open Access ,
Self-coalition graphs
(Wydawnictwa AGH, 2023) Haynes, Teresa W.; Hedetniemi, Jason T.; Hedetniemi, Stephen T.; McRae, Alice A.; Mohan, Raghuveer
A coalition in a graph $G=(V,E)$ consists of two disjoint sets $V_1$ and $V_2$ of vertices, such that neither $V_1$ nor $V_2$ is a dominating set, but the union $V_1 \cup V_2$ is a dominating set of $G$. A coalition partition in a graph $G$ of order $n=|V|$ is a vertex partition $\pi = \{V_1, V_2, \ldots, V_k\}$ such that every set $V_i$ either is a dominating set consisting of a single vertex of degree $n-1$, or is not a dominating set but forms a coalition with another set $V_j$ which is not a dominating set. Associated with every coalition partition $\pi$ of a graph $G$ is a graph called the coalition graph of $G$ with respect to $\pi$, denoted $CG(G,\pi)$, the vertices of which correspond one-to-one with the sets $V_1, V_2, \ldots, V_k$ of $\pi$ and two vertices are adjacent in $CG(G,\pi)$ if and only if their corresponding sets in $\pi$ form a coalition. The singleton partition $\pi_1$ of the vertex set of $G$ is a partition of order $|V|$, that is, each vertex of $G$ is in a singleton set of the partition. A graph $G$ is called a self-coalition graph if $G$ is isomorphic to its coalition graph $CG(G,\pi_{1})$, where $\pi_1$ is the singleton partition of $G$. In this paper, we characterize self-coalition graphs.
Access status: Open Access ,
Upper distance-two domination
(Wydawnictwa AGH, 2025) Hedetniemi, Jason T.; Hedetniemi, Stephen T.; Lewis, Thomas M.
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)$.