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 square grid graphs
183
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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)$.
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.
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
