Let $G$ be a connected $F_k$-free graph of order $n$ with the maximum singless Laplacian spectral radius. Is $G\in Ex(n,F_k)$?
Here, $Ex(n,H)$ denotes the set of $H$-free graphs of order $n$ with $ex(n,H)$ edges.
$\begingroup$
$\endgroup$
9
-
$\begingroup$ If $G$ is connected, the spectral radius increases if an edge is added, so $G\in Ex(n,F_k)$. A disconnected $G$ it can have the same spectral radius, such as two disjoint copies of a graph in $Ex(n,F_k)$. That may or may not be in $Ex(n,F_k)$ depending on what $F_k$ is (you didn't say). $\endgroup$– Brendan McKayCommented Aug 2, 2021 at 11:52
-
$\begingroup$ @BrendanMcKay Thank you so much for the comment. Why the spectral radius increases if an edge is added? $\endgroup$– M.RamanaCommented Aug 2, 2021 at 12:36
-
$\begingroup$ @BrendanMcKay $F_k$ denotes the $k$-fan graph consisting of $k$ triangles which intersect in exactly one common vertex. $\endgroup$– M.RamanaCommented Aug 2, 2021 at 12:37
-
1$\begingroup$ For any connected graph, let $L$ be the signless Laplacian. It is non-negative irreducible so the eigenvector $x$ corresponding to the maximum eigenvalue of $L$ has strictly positive entries. So when adding an edge $\|Lx\|$ becomes larger than before. $\endgroup$– Brendan McKayCommented Aug 2, 2021 at 13:12
-
$\begingroup$ @BrendanMcKay Thanks a lot for your explanation. Could you please introduce me a reference about your comment? $\endgroup$– M.RamanaCommented Aug 4, 2021 at 12:04
|
Show 4 more comments