For a graph $G$, the $2$-token graph $F_2(G)$ has as vertices all $2$-subsets of $V(G)$, with two such subsets adjacent whenever their symmetric difference is an edge of $G$. In this paper, we determine the domination number of the $2$-token graph of the complete bipartite graph $K_{m,n}$, for all integers $2\le m\le n$. We show that it equals $\lceil m/2\rceil+n-1$, except when $m=3$, or when $m\ge5$ is odd and $n=m+1$; in these two exceptional situations it is one less. Our arguments rely on an explicit characterization of the dominating sets of the $2$-token graph of $K_{m,n}$.
This paper is about token graphs and domination number. Let $G=(X,E)$ denote an undirected graph that is connected, with no loops or multiple edges, vertex set $X$, and edge set $E$. Pick a positive integer $k\leq \vert X\vert$. The $k$-token graph of $G$, denoted by $F_k(G)$, is defined as follows. The vertex set $\ma...
Nathaniel Chinman, A. Cortijo, Beatrice Pedroni et al.· 1 citation
We prove that the domination number of the $2$-token graph of the path $P_n$ is $\gamma(F_2(P_n))=d(n)$ for every $n\ge 13$, where $d(n)=\frac1{10}(n^2+5n+c)$ and $c$ is an explicit constant that depends on $n \bmod 5$. This settles a conjecture by Lea\~nos and the authors, who previously proved the upper bound. The lo...
A set $D\subseteq V(G)$ is a $1$-limited dominating set of a graph $G$ if every vertex outside $D$ has a neighbor in $D$ and every vertex of $D$ has at most one neighbor outside $D$. The minimum cardinality among all $1$-limited dominating sets of $G$ is denoted by $\gamma_1^{\mathrm L}(G)$. For every cubic graph $G$ o...
Goran Radić, Gordana Radić, Aleksandra Tepeh· 0 citations
A graph $G$ is $n$-existentially closed or $n$-e.c. if, for all subsets $S\subseteq V(G)$ with $|S|=n$ and for all partitions $S=A\sqcup B$, there exists a vertex in $V(G)\setminus S$ adjacent to all vertices in $A$ and no vertices in $B$. We study the minimum number of edges $m(v,n)$ of a $v$-vertex $n$-e.c. graph, an...
Isabel T. Byrne, John Byrne, S. Cioabă· 0 citations
For integers $n,r,t$ with $2\le t\le r-1$, let $f(n,r,t+1)$ denote the largest possible minimum degree of a balanced $r$-partite graph with parts of size $n$ and containing no copy of $K_{t+1}$. Lo, Treglown and Zhao identified $f(n,7,4)$ as the only remaining case in their treatment of the $K_4$-free family. I determi...
For a graph $G=(V,E)$ of order $n$ and an integer $k$ between $1$ and $\lfloor\frac{n}{2}\rfloor$, its token graph $F_k(G)$ is the graph whose vertices consist of the $\binom{n}{k}$ $k$-subsets of $V$, and two vertices of $F_k(G)$ are adjacent whenever their symmetric difference is an edge in $E$. It was found that the...
Xiao-Di Song, C. Dalf'o, M. Fiol et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
