Sep 2026· Mathematical and Computational Applications· Vol 31, pp. 177· 0 citations· 26 references
Abstract
A graph is called H-free if the graph has no subgraph being isomorphic to H. The classical Turán problem aims to determine the maximum size of an H-free graph with given order. In 2010, Nikiforov introduced the spectral Turán-type problem: determine the maximum spectral radius of an H-free graph with given order. He also presented the following conjecture: for sufficiently large ν and for k≥2, the graph Kk∨(Kν−k−2¯∪K2) is the unique ν-vertex {C2k+1,C2k+2}-free graph having the largest spectral radius, and Kk∨Kν−k¯ is the unique ν-vertex C2k+2-free graph having the largest spectral radius. Recently, this conjecture was confirmed by Cioabă, Desai, and Tait. In this contribution, we resolve Nikiforov’s even cycle conjecture for bipartite graphs. Let ν and k be two integers satisfying ν≥1 if k=1, and ν≥72224k2k−12(k+1)20(2k−3)2k+1k−1 if k≥2. Then, we show that the complete bipartite graph Kk,ν−k uniquely maximizes the spectral radius over the set of C2k+2-free bipartite graphs of order ν.
The existence and construction of distance magic labelings for certain families of complete bipartite graphs are investigated to contribute to the understanding of how arithmetic structure and partition properties influence the existence of distance magic labelings.
Kaveesha V. Senarathna, Sujeeva Wijesiri, S. Almeida· Symmetry· 0 citations
Spectral Tur\'an-type problems ask how the absence of prescribed subgraphs constrains the spectral radius of a matrix associated with a graph. Given a family of graphs $\mathcal{F}$, a graph is called $\mathcal{F}$-free if it contains no member of $\mathcal{F}$ as a subgraph. The theta graph $\theta(l_1,\ldots,l_k)$ co...
The spectral Tur\'an type problem, initiated by Nikiforov in 2007, aims to determine the graphs among $n$-vertex $H$-free graphs having maximum spectral radius. In this paper, we study this problem for $1$-planar graphs, i.e., graphs that admit a drawing in the plane such that each edge is crossed at most once. Recentl...
A graph on \(n\) vertices is called a Parter graph if there exists a nonsingular symmetric matrix, whose nonzero off-diagonal entries correspond exactly to the edges of the graph, such that all of its principal submatrices of order \(n-1\) are singular. Previously, a graph satisfying this condition was said to have pro...
An acyclic edge coloring of a graph G is a proper edge coloring such that G contains no bichromatic cycles. The acyclic chromatic index χa′(G) is the minimum number of colors required for an acyclic edge coloring. Fiamčik and Alon et al. independently conjectured that χa′(G)≤Δ+2 for every simple graph G with maximum de...
A conjecture in [MATCH Commun. Math. Comput. Chem. 89 (2023) 513–530] states that for any unicyclic graph G of order n ≥3, the spectral radius of any degree–based matrix (i.e., a matrix whose entries are functions of vertex degrees) lies between ρ(Cn) and ρ(S+ 3), where S+ 3 denotes the unicyclic graph obtained by atta...
An Jiang, Xue-Wu Zuo, Gen-Jie Wang et al.· Match-communications in Math...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
