Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA spectral characterization of the $s$-clique extension of the triangular graphs
126
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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)$.
rate research
Read More
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.
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 vertex 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 edge 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 no 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
