ترغب بنشر مسار تعليمي؟ اضغط هنا

On the Laplacian spectra of token graphs

66   0   0.0 ( 0 )
 نشر من قبل Ruy Fabila-Monroy
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers $h$ and $k$ such that $1le hle kle frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph $K_n$ and the star $S_{n}=K_{1,n-1}$, respectively. Besides, we obtain a relationship between the spectra of the $k$-token graph of $G$ and the $k$-token graph of its complement $overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph $G$ and its token graph.



قيم البحث

اقرأ أيضاً

150 - Fatihcan M. Atay , Bobo Hua 2014
We study the symmetry properties of the spectra of normalized Laplacians on signed graphs. We find a new machinery that generates symmetric spectra for signed graphs, which includes bipartiteness of unsigned graphs as a special case. Moreover, we pro ve a fundamental connection between the symmetry of the spectrum and the existence of damped two-periodic solutions for the discrete-time heat equation on the graph.
124 - Minjie Zhang , Shuchao Li 2015
In this paper, we use a new and correct method to determine the $n$-vertex $k$-trees with the first three largest signless Laplacian indices.
The emph{simplicial rook graph} SR(d,n) is the graph whose vertices are the lattice points in the $n$th dilate of the standard simplex in $mathbb{R}^d$, with two vertices adjacent if they differ in exactly two coordinates. We prove that the adjacency and Laplacian matrices of SR(3,n) have integral spectrum for every $n$. The proof proceeds by calculating an explicit eigenbasis. We conjecture that SR(d,n) is integral for all $d$ and $n$, and present evidence in support of this conjecture. For $n<binom{d}{2}$, the evidence indicates that the smallest eigenvalue of the adjacency matrix is $-n$, and that the corresponding eigenspace has dimension given by the Mahonian numbers, which enumerate permutations by number of
The Laplacian spread of a graph is the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. We find that the class of strongly regular graphs attains the maximum of largest eigenvalues, th e minimum of second-smallest eigenvalues of Laplacian matrices and hence the maximum of Laplacian spreads among all simple connected graphs of fixed order, minimum degree, maximum degree, minimum size of common neighbors of two adjacent vertices and minimum size of common neighbors of two nonadjacent vertices. Some other extremal graphs are also provided.
205 - Xiaogang Liu , Pengli Lu 2014
Let $P_n$ and $C_n$ denote the path and cycle on $n$ vertices respectively. The dumbbell graph, denoted by $D_{p,k,q}$, is the graph obtained from two cycles $C_p$, $C_q$ and a path $P_{k+2}$ by identifying each pendant vertex of $P_{k+2}$ with a ver tex of a cycle respectively. The theta graph, denoted by $Theta_{r,s,t}$, is the graph formed by joining two given vertices via three disjoint paths $P_{r}$, $P_{s}$ and $P_{t}$ respectively. In this paper, we prove that all dumbbell graphs as well as theta graphs are determined by their Laplacian spectra.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا