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 $\mathcal{X}$ consists of all $k$-subsets of $X$. Two vertices $x,y\in \mathcal{X}$ are adjacent whenever the symmetric difference of $x$ and $y$ consists of two vertices that form an edge in $E$. In this paper, we compute the exact value for the domination number of $F_2(K_{m,n})$ where $K_{m,n}$ is the complete bipartite graph with parameters $m,n$. We present some bounds for the domination number of $F_k(K_{m,n})$ when $k\geq 3$.
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...
E. Troncoso, I. Caldera, L. M. Rivera· 0 citations
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
For a family $\mathcal{F}$ of $k$-graphs, $ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n\g...
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
Let $G$ be a connected graph. The $k$-token graph of $G$ is the graph $F_k(G)$ whose vertex set consists of all subsets of $k$ vertices of $G$, where two of them are adjacent whenever their symmetric difference is an edge of $G$. Every automorphism of $G$ induces one of $F_k(G)$, as does complementation when $k=|G|/2$;...
R. Fabila-Monroy, S. G. Gómez-Galicia, A. Trujillo-Negrete· 1 citation· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
