On the 2-token graph of a graph

Abstract

Let $G=(V,E)$ be a graph and let $k$ be a positive integer. Let $P_k\left(V\right)$=$\{S:S\subseteq V$ and $\left|S\right|=k\}$. The $k$-token graph $F_k\left(G\right)$ is the graph with vertex set $P_k\left(V\right)$ and two vertices $A$ and $B$ are adjacent if $A\Delta B=\{a,b\}$ and $ab\in E\left(G\right)$, where $\Delta$ denotes the symmetric difference. In this paper we present several basic results on 2-token graphs.

Keywords:

• $k$-token graph
• Line graph
• Chordal graph
• Independence number

1 Introduction

By a graph $G=(V,E)$ we mean a finite undirected graph with neither loops nor multiple edges. The order $\left|V\right|$ and the size $\left|E\right|$ are denoted by $n$ and $m$ respectively. For graph theoretic terminology we refer to Chartrand and Zhang [1].

For any set $V$ we denote by $P_k\left(V\right)$ the set of all $k$-element subsets of $V$. Monray et al. [2] introduced the notion of $k$-token graph of a graph $G$.

Definition 1.1

[2] Let $G=(V,E)$ be a graph and let $k\ge 1$ be an integer. The $k$-token graph $F_k\left(G\right)$ of $G$ is the graph with vertex set $P_k\left(V\right)$ and two vertices $A$ and $B$ are adjacent if $A\Delta B=\{a,b\}$ where $ab\in E\left(G\right)$.

Clearly $\left|V\left(F_k\left(G\right)\right)\right|=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ and $\left|E\left(F_k\left(G\right)\right)\right|=\left(\genfrac{}{}{0ex}{}{n-2}{k-1}\right)\left|E\left(G\right)\right|$.

We need the following theorems.

Theorem 1.2

[2] If $F_k\left(G\right)$ is bipartite for some $k\ge 1$ , then $F_l\left(G\right)$ is bipartite for all $l\ge 1$ .

Theorem 1.3

[3] Let $G=(V,E)$ be a graph of order $n$ and let $v_i,v_j\in V$ . Then $$de{g}_{F_2\left(G\right)}\left(\{v_i,v_j\}\right)=\left\{\begin{array}{cc}deg\left(v_i\right)+deg\left(v_j\right)\hfill & \text{if}{v}_i{v}_j\notin E\hfill \\ deg\left(v_i\right)+deg\left(v_j\right)-2\hfill & \text{if}{v}_i{v}_j\in E\hfill \end{array}\right.$$

In this paper we investigate the 2-token graph $F_2\left(G\right)$. We repeatedly use the following observation.

Observation 1.4

Two vertices $x$ and $y$ of $F_2\left(G\right)$ are adjacent if and only if $x=\{a,b\}$ and $y=\{a,c\}$ with $bc\in E\left(G\right)$ .

2 Main results

We first prove that for complete graphs the 2-token graph is its line graph.

Theorem 2.1

Let $G$ be a graph of order $n\ge 2$ . Then $F_2\left(G\right)$ is isomorphic to the line graph $L\left(G\right)$ if and only if $G=K_n$ .

Proof

Suppose $G=K_n$. Let $\{v_i,v_j\}\in V\left(F_2\left(G\right)\right)$. Since $v_i{v}_j\in E\left(G\right)$, it follows that $\{v_i,v_j\}$ is adjacent to $\{v_i,v_k\}$ and $\{v_j,v_k\}$ for all $k\ne i,j$. Thus $N_{F_2\left(G\right)}\left(\{v_i,v_j\}\right)=N_{L\left(G\right)}\left(v_i{v}_j\right)$. Hence $F_2\left(G\right)$ is isomorphic to $L\left(G\right)$. Conversely, suppose that $F_2\left(G\right)=L\left(G\right)$. Then $\left|E\left(G\right)\right|=\left|V\left(L\left(G\right)\right)\right|=\left|V\left(F_2\left(G\right)\right)\right|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and hence it follows that $G=K_n$.

Lemma 2.2

If a graph $G$ contains two vertex disjoint paths $P_2=(v_1,v_2)$ and $P_r=(w_1,w_2,\dots ,w_r)$ , then $F_2\left(G\right)$ contains a cycle of length $2r$ .

Proof

Let $X_i=\{v_1,w_i\}$ and $Y_i=\{v_2,w_i\}$ where $1\le i\le r$. Then $(X_1,X_2,\dots$, $X_r,Y_r,Y_{r-1},\dots ,Y_2,Y_1,X_1\}$ is a cycle of length $2r$ in $F_2\left(G\right)$.

Observation 2.3

If $v_1{w}_1$ and $v_2{w}_2$ are two nonadjacent edges in $G$ , then the corresponding cycle $C_4$ given in Lemma 2.2 is an induced cycle.

Lemma 2.4

Let $G=(V,E)$ be a graph. Then $G$ is triangle free if and only if $F_2\left(G\right)$ is triangle free.

Proof

Suppose $G$ is triangle free. If $F_2\left(G\right)$ contains a triangle say $(\{v_1,v_2\}$, $\{v_1,v_3\},\{v_3,v_2\},\{v_1,v_2\})$, then $(v_1,v_2,v_3,v_1)$ is a triangle in $G$ which is a contradiction. The proof of the converse is similar.

In the following theorems we obtain a characterization of graph $G$ for which $F_2\left(G\right)$ is a tree or chordal graph.

Theorem 2.5

Let $G$ be a graph of order $n\ge 2$ . Then $F_2\left(G\right)$ is a tree if and only if $G=P_2$ or $P_3$ .

Proof

If $G=P_2$, then $F_2\left(G\right)=K_1$. If $G=P_3$, then $F_2\left(G\right)=P_3$. Conversely, suppose $F_2\left(G\right)$ is a tree. If there exist two nonadjacent edges $v_1{v}_2$ and $v_3{v}_4$ in $G$, then $(\{v_3,v_1\},\{v_3,v_2\},\{v_2,v_4\},\{v_1,v_4\},\{v_3,v_1\})$ is a cycle in $F_2\left(G\right)$, which is a contradiction. Hence any two edges in $G$ are adjacent. Thus $G=K_3$ or $K_{1,n}$. If $G=K_3$, then $F_2\left(G\right)=K_3$. Now suppose $G=K_{1,n}$ where $n\ge 3$. Let $v_1$ be the centre and let $v_2,v_3,\dots ,v_n$ be the pendent vertices of $G$. Then $(\{v_1,v_2\},\{v_2,v_3\},\{v_1,v_3\},\{v_3,v_4\},\{v_1,v_4\},\{v_2,v_4\},\{v_1,v_2\})$ is the cycle $C_6$ in $F_2\left(G\right)$, which is a contradiction. Hence $G=K_{1,n}$ where $n\le 2$. Thus $G=P_2$ or $P_3$.

Theorem 2.6

Let $G$ be a connected graph of order $n$ and let $n\ge 2$ . Then $F_2\left(G\right)$ is a chordal graph if and only if $G$ is isomorphic to one of the graphs $P_2,P_3$ or $K_3$ .

Proof

Suppose $F_2\left(G\right)$ is a chordal graph. It follows from Observation 2.3 that any two edges of $G$ are adjacent. Now proceeding as in the proof of Theorem 2.5 we get $G=P_2,P_3$ or $K_3$. The converse is obvious.

In the following theorem we obtain a lower bound for the independence number of $F_2\left(G\right)$.

Theorem 2.7

Let $G$ be a connected graph of order $n$ with ${\beta }_0\left(G\right)\ge 2$ . Then ${\beta }_0\left(F_2\left(G\right)\right)\ge \left(\genfrac{}{}{0ex}{}{{\beta }_0\left(G\right)}{2}\right)+⌊\frac{n-{\beta }_0\left(G\right)}{2}⌋$ and the bound is sharp.

Proof

Let $S$ be a ${\beta }_0$-set of $G$. Let $S_1=\{\{u_i,u_j\}:u_i,u_j\in S\}$ and let $S_2$ be a collection of disjoint 2-element subsets of $V-S$. Clearly $\left|S_2\right|=⌊\frac{n-{\beta }_0\left(G\right)}{2}⌋$. Let $T=S_1\cup S_2$. Let $\{u_i,u_j\},\{u_i,u_k\}\in S_1$. Since $u_j{u}_k\notin E\left(G\right)$, it follows that $\{u_i,u_j\}$ is not adjacent to $\{u_i,u_k\}$ in $F_2\left(G\right)$. Obviously no element $x$ of $S_2$ is adjacent with any element of $T-\left\{x\right\}$. Hence $T$ is an independent set of $F_2\left(G\right)$. Thus ${\beta }_0\left(F_2\left(G\right)\right)\ge \left|T\right|=\left(\genfrac{}{}{0ex}{}{{\beta }_0\left(G\right)}{2}\right)+⌊\frac{n-{\beta }_0\left(G\right)}{2}⌋$. We observe that if $G=K_4-e$, then ${\beta }_0\left(G\right)=2$ and ${\beta }_0\left(F_2\left(G\right)\right)=2$, which shows that the above bound is sharp.

Theorem 2.8

Let $G$ be a graph of order $n$ . If there exists a vertex $v_1\in V\left(G\right)$ such that $deg{v}_1=2$ , then $G$ is isomorphic to a subgraph of $F_2\left(G\right)$ .

Proof

Let $N\left(v_1\right)=\{v_2,v_3\}$. Let $S=\{\{v_1,v_i\}:i\ge 2\}$. Clearly the subgraph of $F_2\left(G\right)$ induced by $S$ is isomorphic $G-\left\{v_1\right\}$. Now $\{v_2,v_3\}$ is adjacent to $\{v_1,v_2\}$ and $\{v_1,v_3\}$ in $F_2\left(G\right)$. Hence the subgraph of $F_2\left(G\right)$ induced by the set $S\cup \left\{\{v_2,v_3\}\right\}$ is isomorphic to $G$.

Observation 2.9

The graph $F_2\left(K_4\right)$ does not contain an induced subgraph isomorphic to $K_4$ . This shows that Theorem 2.8 is not true if $G$ has no vertex of degree 2.

Theorem 2.10

A connected graph $H$ is isomorphic to $F_2\left(K_{1,n-1}\right)$ if and only if the following conditions are satisfied.

(i)	$H$ is a bipartite graph of order $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ with bipartition $V_1,V_2$ where $\left|V_1\right|=n-1$ and $\left|V_2\right|=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ .
(ii)	Every vertex of $V_1$ has degree $n-2$ .
(iii)	Every vertex of $V_2$ has degree 2.
(iv)	Any two vertices of $V_1$ have exactly one common neighbour.

Proof

Let $H=F_2\left(G\right)$ where $G=K_{1,n-1}$. Let $v_1$ be the centre of the star. Let $\{v_2,v_3,\dots ,v_n\}$ be the set of pendent vertices of $G$.

(i) Let $V_1=\{\{v_1,v_i\}:2\le i\le n\}$ and let $V_2=P_2\left(V\right)-V_1$ where $P_2\left(V\right)$ is the set of all 2-element subsets of $V$. Clearly $\left|V_1\right|=n-1$ and $\left|V_2\right|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-(n-1)=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$. Since $v_i,v_j\notin E\left(G\right)$ if $i,j\ne 1$, it follows that $\{v_1,v_i\}$ is not adjacent to $\{v_1,v_j\}$ in $H$. Hence $V_1$ is independent.

Now, let $\{v_i,v_j\}$ and $\{v_k,v_i\}\in V_2$ since $i,k,j\ne 1$, it follows that $v_j{v}_k\notin E\left(G\right)$. Hence $\{v_i,v_j\}$ is not adjacent to $\{v_k,v_i\}$ in $H$. Hence $V_2$ is independent. This proves (i).

(ii) Let $\{v_1,v_i\}\in V_1$. The vertices adjacent to $\{v_1,v_i\}$ in $H$ are given by $\{v_k,v_i\}$ for any $k\ne 1,i$. Hence every vertex of $V_1$ has degree $n-1$.

(iii) Let $\{v_r,v_s\}\in V_2$. Hence $s,r\ne 1$. The vertices adjacent to $\{v_r,v_s\}$ are $\{v_1,v_r\}$ and $\{v_1,v_s\}$. Hence any vertex of $V_2$ has degree 2.

(iv) Let $\{v_i,v_j\},\{v_1,v_j\}\in V_1$. Clearly $\{v_i,v_j\}$ is the unique common neighbour.

Conversely, suppose $H$ satisfies the conditions (i), (ii), (iii) and (iv). Suppose $H=F_2\left(G\right)$ for some $G$. Since $\left|V\left(H\right)\right|=n-1+\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, it follows that $\left|V\left(G\right)\right|=n$. Now, let $m=\left|E\left(G\right)\right|$. Hence the number of edges in $H$ is $(n-2)m$. But $\left|E\left(H\right)\right|=2\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)=(n-1)(n-2)$. Hence it follows that $m=n-1$, so that $G$ is a tree.

Suppose $G$ has 2 nonadjacent edges say $v_1{v}_2$ and $v_3{v}_4$. Then $(\{v_1,v_3\}$, $\{v_2,v_3\},\{v_2,v_4\},\{v_1,v_4\},\{v_4,v_3\})$ is a cycle in $H$. Hence $\{v_1,v_3\}$ and $\{v_2,v_4\}$ have $\{v_2,v_3\}$ and $\{v_1,v_4\}$ as common neighbours which contradicts (iv).

Hence it follows that $G$ is star $K_{1,n-1}$.

Theorem 2.11

Let $G=(V,E)$ be a connected graph of order $n$ . Then $G$ is bipartite if and only if $F_2\left(G\right)$ is bipartite.

Proof

Suppose $G$ is bipartite. Let $V_1,V_2$ be the bipartition of $V\left(G\right)$. If $\left|V_1\right|=1$, then $G=K_{1,n-1}$ and hence it follows from Theorem 2.10 that $F_2\left(G\right)$ is bipartite.

Suppose $\left|V_1\right|\ge 2$ and $\left|V_2\right|\ge 2$. Let $X=P_2\left(V_1\right)\cup P_2\left(V_2\right)$ and $Y=V\left(F_2\left(G\right)\right)-X$. We claim that $X,Y$ is a bipartition of $F_2\left(G\right)$. Since $V_1$ and $V_2$ are independent sets in $G$, it follows from Theorem 2.7 that $P_2\left(V_1\right)$ and $P_2\left(V_2\right)$ are independent sets in $F_2\left(G\right)$. Further any element of $P_2\left(V_1\right)$ is not adjacent to any element of $P_2\left(V_2\right)$. Hence $X$ is independent.

Theorem 2.12

The cycle $C_r$ is $F_2\left(G\right)$ for some graph $G$ if and only if $r=3$ or 6.

Proof

Obviously $F_2\left(C_3\right)=C_3$ and $F_2\left(K_{1,3}\right)=C_6$. Conversely, suppose $C_r=F_2\left(G\right)$ for some graph $G$. Let $\left|V\left(G\right)\right|=n$. Now since $F_2\left(G\right)$ is $C_4$ free, it follows from Lemma 2.2 that any two edges in $G$ are adjacent. Hence $G=K_{1,n}$ or $K_3$. If $n\ge 4$, then $deg(v_1,v_5)\ge 3$ where $v_1$ is the centre of $K_{1,n}$ which is a contradiction. Hence $n=3$. Thus $G=K_{1,3}$ or $C_3$. Hence $F_2\left(G\right)=C_3$ or $C_6$.

3 Conclusion and scope

We observe that if $H=F_2\left(G\right)$ for some graph $G$ of order $n$ then $\left|V\left(H\right)\right|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. The following fundamental problem arises naturally.

Problem 3.1

If $H$ is a graph of order $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, obtain a necessary and sufficient condition for the existence of a graph $G$ of order $n$ such that $H=F_2\left(G\right)$.

Theorem 2.7 gives a bound for ${\beta }_0\left(F_2\left(G\right)\right)$ and leads to the following problem.

Problem 3.2

Characterize graphs $G$ for which ${\beta }_0\left(F_2\left(G\right)\right)=\left(\genfrac{}{}{0ex}{}{{\beta }_0\left(G\right)}{2}\right)+⌊\frac{n-{\beta }_0\left(G\right)}{2}⌋$.