Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrongly cospectral vertices in normal Cayley graphs
178
0
0.0
(
0
)
Publication date
2021
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove an upper bound on the number of pairwise strongly cospectral vertices in a normal Cayley graph, in terms of the multiplicities of its eigenvalues. We use this to determine an explicit bound in Cayley graphs of $mathbb{Z}_2^d$ and $mathbb{Z}_4^d$. We also provide some infinite families of Cayley graphs of $mathbb{Z}_2^d$ with a set of four pairwise strongly cospectral vertices and show that such graphs exist in every dimension.
rate research
Read More
We generalize Schwenks result that almost all trees contain any given limb to trees with positive integer vertex weights. The concept of characteristic polynomial is extended to such weighted trees and we prove almost all weighted trees have a cospectral mate. We also prove almost all trees contain $k$ cospectral vertices for any integer $kge2$.
Following a problem posed by Lovasz in 1969, it is believed that every connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from groups having a $(2,s,3)$-presentation, that is, for groups $G=la a,b| a^2=1, b^s=1, (ab)^3=1, etc. ra$ generated by an involution $a$ and an element $b$ of order $sgeq3$ such that their product $ab$ has order 3. More precisely, it is shown that the Cayley graph $X=Cay(G,{a,b,b^{-1}})$ has a Hamilton cycle when $|G|$ (and thus $s$) is congruent to 2 modulo 4, and has a long cycle missing only two vertices (and thus necessarily a Hamilton path) when $|G|$ is congruent to 0 modulo 4.
In this paper, we construct an infinite family of normal Cayley graphs, which are $2$-distance-transitive but neither distance-transitive nor $2$-arc-transitive. This answers a question raised by Chen, Jin and Li in 2019 and corrects a claim in a literature given by Pan, Huang and Liu in 2015.
In this paper we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible automorphism group: that is, it is a digraphical regular representation (DRR). In this paper, we approach the corresponding question for undirected Cayley graphs. The situation is complicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing separately the cases where the regular group $R$ has a nontrivial proper normal subgroup $N$ with the property that the automorphism group of the digraph fixes each $N$-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup.
A Cayley (di)graph $Cay(G,S)$ of a group $G$ with respect to $S$ is said to be normal if the right regular representation of $G$ is normal in the automorphism group of $Cay(G,S)$, and is called a CI-(di)graph if there is $alphain Aut(G)$ such that $S^alpha=T$, whenever $Cay(G,S)cong Cay(G,T)$ for a Cayley (di)graph $Cay(G,T)$. A finite group $G$ is called a DCI-group or a NDCI-group if all Cayley digraphs or normal Cayley digraphs of $G$ are CI-digraphs, and is called a CI-group or a NCI-group if all Cayley graphs or normal Cayley graphs of $G$ are CI-graphs, respectively. Motivated by a conjecture proposed by Adam in 1967, CI-groups and DCI-groups have been actively studied during the last fifty years by many researchers in algebraic graph theory. It takes about thirty years to obtain the classification of cyclic CI-groups and DCI-groups, and recently, the first two authors, among others, classified cyclic NCI-groups and NDCI-groups. Even though there are many partial results on dihedral CI-groups and DCI-groups, their classification is still elusive. In this paper, we prove that a dihedral group of order $2n$ is a NCI-group or a NDCI-group if and only if $n=2,4$ or $n$ is odd. As a direct consequence, we have that if a dihedral group $D_{2n}$ of order $2n$ is a DCI-group then $n=2$ or $n$ is odd-square-free, and that if $D_{2n}$ is a CI-group then $n=2,9$ or $n$ is odd-square-free, throwing some new light on classification of dihedral CI-groups and DCI-groups.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
