The complementary prism $G\overline{G}$ of a graph $G$ is obtained from the disjoint union of $G$ and its complement $\overline{G}$ by adding an edge between each vertex $a$ in $G$ and its copy $a'$ in $\overline{G}.$ This paper explores a general framework for studying fractional revival with respect to real symmetric matrices with a block structure. The framework is then used to show that, for a fixed state $\mathbf{u}$ in $G$ orthogonal to the all-one vector, the complementary prism $G\overline{G}$ exhibits fractional revival from the state $[\mathbf{u},\mathbf{0}]^T$ with respect to the adjacency, Laplacian, and signless Laplacian matrices. We further characterize perfect pair state transfer in the complementary prism of a complete graph and establish the existence of perfect pair and plus state transfer in the complementary prism of a complete bipartite graph.
Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(G)$ be the Cayley graph of the symmetric group $S_n$ generated by the transpositions corresponding to the edges of $G$. We study the inverse spectral problem for the assignment $G\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{...
A paired dominating set of a graph $G$ is a dominating set $D$ such that $G[D]$ has a perfect matching. The minimum size of such a set is the paired domination number $\gpr(G)$. Desormeaux and Henning conjectured that every cubic bipartite graph $G$ of order $n$ satisfies $\gpr(G)\le n/2$. We prove the conjecture in th...
For a graph $G$, we investigate sufficient degree conditions under which either $G$ or its complement $\overline{G}$ is $k$-connected. Motivated by a theorem of Hellwig and Volkmann, we introduce the notion of complement connectivity admissible pairs and define the parameter $\mathcal{C}(k)$ as the minimum degree thres...
The energy $\mathcal{E}(\Gamma)$ of a signed graph $\Gamma=(G,\sigma)$ is the sum of the absolute values of the eigenvalues of its adjacency matrix $A(\Gamma)$. In this article, we prove that $\mathcal{E}(\Gamma)\geq 2\tau(G)$, where $\tau(G)$ is the vertex cover number of $G$. The case of unsigned graphs, a 1980s conj...
Aniruddha Samanta, Deepshikha, K. Das· 0 citations
Let $\rho(G)$ denote the signless Laplacian spectral radius of a graph $G$, and let $\mathcal C_{n,m}$ be the family of connected graphs of order $n$ and size $m$. A graph is $Q$-maximal if it maximizes $\rho(G)$ over this family. Motivated by a question of Chang and Tam (2011), we study this extremal problem using sca...
Di-Jian Wang, Hong Ge, Shi-Cai Gong et al.· 0 citations
A family of paths in a graph $G$ strongly separates the edges of $G$ if for every ordered pair of distinct edges $(e,f)$ some path in the family contains $e$ and avoids $f$; the minimum size of such a family is denoted by $\operatorname{ssp}(G)$. Bonamy, Botler, Dross, Naia, and Skokan proved, for every $n$-vertex grap...
Daniel W. Cranston, Jared Noyman, G. Yu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.