Independence and matching numbers of some token graphs
Independence and matching numbers of some token graphs
复制标题
一些token图的独立性和匹配数
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Luis Manuel Rivera
中科院分区：
文献类型：
--
作者：
H. D. Alba;W. Carballosa;J. Leaños;Luis Manuel Rivera
设$G$是一个阶为$n$的简单图，$k$是一个整数，使得$1 \leq k \leq n-1$。G的k-令牌图F_k（G），即G的k-次对称幂，定义为顶点集为V（G）的所有k-子集的图，其中两个顶点在F_k（G）中相邻，只要它们的对称差是G的一条边.本文研究了F_k（G）的独立性和匹配数。我们首先给出了$F_k（G）$的匹配数$\nu（F_k（G））$的一个紧下界，在这个下界中$G$有完美匹配或几乎完美匹配。利用这个结果，我们估计了一类二部$k$-令牌图的独立数，并确定了$G \in \{Pm，K_{1，m}，K_{m，m}，K_{m，m+1}\}和$1 \leq k \leq中$\beta（F_2（K_{m，n}）），\beta（F_2（C_n））$和$\beta（F_k（G））$的精确值|G|- 一美元
Let $G$ be a simple graph of order $n$ and let $k$ be an integer such that $1 \leq k \leq n-1$. The $k$-token graph $F_k(G)$ of $G$, or the $k$-$th$ symmetric power of $G$, is defined as the graph with vertex set all $k$-subsets of $V(G)$, where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is an edge of $G$. Here we study the independence and matching numbers of $F_k(G)$. We start by giving a tight lower bound for the matching number $\nu(F_k(G))$ of $F_k(G)$ for the case in which $G$ has either a perfect matching or an almost perfect matching. Using this result, we estimate the independence number for a large class of bipartite $k$-token graphs, and determine the exact value of $\beta(F_2(K_{m,n})), \beta(F_2(C_n))$ and $\beta(F_k(G))$ for $G \in \{P_m, K_{1, m}, K_{m, m}, K_{m, m+1}\}$ and $1 \leq k \leq |G|-1$.