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

A spectral characterization of the s-clique extension of the square grid graphs

183   0   0.0 ( 0 )
 نشر من قبل Sakander Hayat
 تاريخ النشر 2018
  مجال البحث
والبحث باللغة English




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

In this paper we show that for integers $sgeq2$, $tgeq1$, any co-edge-regular graph which is cospectral with the $s$-clique extension of the $ttimes t$-grid is the $s$-clique extension of the $ttimes t$-grid, if $t$ is large enough. Gavrilyuk and Koolen used a weaker version of this result to show that the Grassmann graph $J_q(2D,D)$ is characterized by its intersection array as a distance-regular graph, if $D$ is large enough.



قيم البحث

اقرأ أيضاً

A regular graph is co-edge regular if there exists a constant $mu$ such that any two distinct and non-adjacent vertices have exactly $mu$ common neighbors. In this paper, we show that for integers $sge 2$ and $n$ large enough, any co-edge-regular gra ph which is cospectral with the $s$-clique extension of the triangular graph $T((n)$ is exactly the $s$-clique extension of the triangular graph $T(n)$.
218 - 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.
Let $G$ be a graph whose edges are coloured with $k$ colours, and $mathcal H=(H_1,dots , H_k)$ be a $k$-tuple of graphs. A monochromatic $mathcal H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edg e or forms a monochromatic copy of $H_i$ in colour $i$, for some $1le ile k$. Let $phi_{k}(n,mathcal H)$ be the smallest number $phi$, such that, for every order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $mathcal H$-decomposition with at most $phi$ elements. Extending the previous results of Liu and Sousa [Monochromatic $K_r$-decompositions of graphs, Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $mathcal H$ is a clique and $nge n_0(mathcal H)$ is sufficiently large.
In this paper we give two characterizations of the $p times q$-grid graphs as co-edge-regular graphs with four distinct eigenvalues.
Let $q_{min}(G)$ stand for the smallest eigenvalue of the signless Laplacian of a graph $G$ of order $n.$ This paper gives some results on the following extremal problem: How large can $q_minleft( Gright) $ be if $G$ is a graph of order $n,$ with n o complete subgraph of order $r+1?$ It is shown that this problem is related to the well-known topic of making graphs bipartite. Using known classical results, several bounds on $q_{min}$ are obtained, thus extending previous work of Brandt for regular graphs. In addition, using graph blowups, a general asymptotic result about the maximum $q_{min}$ is established. As a supporting tool, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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