Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe uniqueness of covers for widely generalized line graphs
103
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
As a natural generalization of line graphs, Hoffman line graphs were defined by Woo and Neumaier. Especially, Hoffman line graphs are closely related to the smallest eigenvalue of graphs, and the uniqueness of strict covers of a Hoffman line graph plays a key role in such a study. In this paper, we prove a theorem for the uniqueness of strict covers under a condition which can be checked in finite time. Our result gives a generalization and a short proof for the main part of [Ars Math.~Contemp. textbf{1} (2008) 81--98].
rate research
Read More
We solve a problem posed by Cardinali and Sastry [2] about factorization of $2$-covers of finite classical generalized quadrangles. To that end, we develop a general theory of cover factorization for generalized quadrangles, and in particular we study the isomorphism problem for such covers and associated geometries. As a byproduct, we obtain new results about semipartial geometries coming from $theta$-covers, and consider related problems.
In this paper, which is a sequel to cite{part1}, we proceed with our study of covers and decomposition laws for geometries related to generalized quadrangles. In particular, we obtain a higher decomposition law for all Kantor-Knuth generalized quadrangles which generalizes one of the main results in cite{part1}. In a second part of the paper, we study the set of all Kantor-Knuth ovoids (with given parameter) in a fixed finite parabolic quadrangle, and relate this set to embeddings of parabolic quadrangles into Kantor-Knuth quadrangles. This point of view gives rise to an answer of a question posed in cite{JATSEP}.
This paper disproves a conjecture of Wang, Wu, Yan and Xie, and answers in negative a question in Dvorak, Pekarek and Sereni. In return, we pose five open problems.
The r-th power of a graph modifies a graph by connecting every vertex pair within distance r. This paper gives a generalization of the Alon-Boppana Theorem for the r-th power of graphs, including irregular graphs. This leads to a generalized notion of Ramanujan graphs, those for which the powered graph has a spectral gap matching the derived Alon-Boppana bound. In particular, we show that certain graphs that are not good expanders due to local irregularities, such as Erdos-Renyi random graphs, become almost Ramanujan once powered. A different generalization of Ramanujan graphs can also be obtained from the nonbacktracking operator. We next argue that the powering operator gives a more robust notion than the latter: Sparse Erdos-Renyi random graphs with an adversary modifying a subgraph of log(n)^c$ vertices are still almost Ramanujan in the powered sense, but not in the nonbacktracking sense. As an application, this gives robust community testing for different block models.
It is proved that if a graph is regular of even degree and contains a Hamilton cycle, or regular of odd degree and contains a Hamiltonian $3$-factor, then its line graph is Hamilton decomposable. This result partially extends Kotzigs result that a $3$-regular graph is Hamiltonian if and only if its line graph is Hamilton decomposable, and proves the conjecture of Bermond that the line graph of a Hamilton decomposable graph is Hamilton decomposable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
