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

A spectral characterization of the $s$-clique extension of the triangular graphs

126   0   0.0 ( 0 )
 نشر من قبل Ying-Ying Tan
 تاريخ النشر 2019
  مجال البحث
والبحث باللغة English




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

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 graph 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)$.



قيم البحث

اقرأ أيضاً

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 Koo len 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.
203 - 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.
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.
Given a graph $G$, the strong clique number of $G$, denoted $omega_S(G)$, is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the line graph of $G$. As a relaxation of the renowned ErdH{o}s--Nev{ s}etv{r}il conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$-free graph, then $omega_S(G)leq (2k-1)Delta(G)-{2k-1choose 2}$, and if $G$ is a $C_{2k}$-free bipartite graph, then $omega_S(G)leq kDelta(G)-(k-1)$. We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a ${C_5, C_{2k}}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq kDelta(G)-(k-1)$, when either $kgeq 4$ or $kin {2,3}$ and $G$ is also $C_3$-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $kgeq 3$, we prove that a $C_{2k}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq (2k-1)Delta(G)+(2k-1)^2$. This improves some results of Cames van Batenburg, Kang, and Pirot.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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