A quasi-strongly regular graph of grade 2 with parameters (n,k,a;c1,c2) is a k-regular graph on n vertices such that every pair of adjacent vertices have a common neighbours, every pair of distinct ...nonadjacent vertices have c1 or c2 common neighbours, and for each ci(i=1,2), there exists a pair of non-adjacent vertices sharing ci common neighbours. If a quasi-strongly regular graph is neither a strongly regular graph nor a Deza graph, then it is called a strictly quasi-strongly regular graph. In earlier papers, we characterised the strictly quasi-strongly regular graphs with parameters (n,k,a;k−2,c2) satisfying a≥k−5. In this paper, we characterize strictly quasi-strongly regular graphs with parameters (n,k,a;k−2,c2) satisfying a<k−5 and l1>2, where l1 is the number of vertices with k−2 common neighbours with a given vertex.
A quasi-strongly regular graph G of grade 2 with parameters (n,k,a;c1,c2) is a k-regular graph on n vertices such that every pair of adjacent vertices have a common neighbors, every pair of distinct ...nonadjacent vertices have c1 or c2 common neighbors, and for each ci(i=1,2), there exists a pair of non-adjacent vertices sharing ci common neighbors. The children G1 and G2 of the graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in G1 or G2 if and only if they share c1 or c2 neighbors, respectively. The graph G is a quasi-strongly regular graph of type A or B if it is of grade 2 and has a child that is a connected strongly regular graph or a disjoint union of cliques of order m(m>1), respectively. In this paper, we investigate the spectral properties of the graph G if it is a quasi-strongly regular graph of type A or B. Several examples of distance-regular graphs which are quasi-strongly regular graphs of type A are given. Moreover, we give several constructions of quasi-strongly regular graphs and calculate their spectrum.
We study how few longest cycles a regular graph can have under additional constraints. For each integer r≥5, we give exponential improvements for the best asymptotic upper bounds for this invariant ...under the additional constraint that the graphs are r-regular hamiltonian graphs. Earlier work showed that a conjecture by Haythorpe (2018) on a lower bound for this invariant is false because of an incorrect constant factor, whereas our results imply that the conjecture is even asymptotically incorrect. Motivated by a question of Zamfirescu (2022) and work of Chia and Thomassen (2012), we also study this invariant for non-hamiltonian 2-connected r-regular graphs and show that in this case the invariant can be bounded from above by a constant for all large enough graphs, even for graphs with arbitrarily large girth.
Let
be a diameter 3 distance-regular graph with a strongly regular graph
, where
is the graph whose vertex set coincides with the vertex set of the graph
and two vertices are adjacent whenever they ...are at distance 3 in the graph
. Computing the parameters of
by the intersection array of the graph
is considered as the direct problem. Recovering the intersection array of the graph
by the parameters of
is referred to as the inverse problem. The inverse problem for
has been solved earlier by A. A. Makhnev and M. S. Nirova. In the case where
is a pseudo-geometric graph of a net, a series of admissible intersection arrays has been obtained: {
−
) + 2
−
− 1,
−
), (
− 1)(
−
) + 2
−
; 1,
,
−
} (A. A. Makhnev, Wenbin Guo, M. P. Golubyatnikov). The cases
= 1 and
= 2 have been examined by A. A. Makhnev, M. P. Golubyatnikov and A. A. Makhnev, M. S. Nirova, respectively.
In this paper in the class of graphs with the intersection arrays {
− 1, (
− 1)(
+ 1)}, {
−
+ 1}; 1, 1, (
− 1)(
+ 1)} all admissible intersection arrays for {3 ≤ m ≤ 13} are found: {20,16,5; 1, 1,16}, {39,36,4; 1, 1,36}, {55,54,2; 1, 2,54}, {90,84,7; 1, 1,84}, {220,216,5; 1, 1,216}, {272,264,9; 1, 1,264} and {350,336,15; 1, 1,336}. It is demonstrated that graphs with the intersection arrays {20,16,5; 1, 1,16}, {39,36,4; 1, 1,36} and {90,84,7; 1, 1,84} do not exist.
Designs over edge-regular, co-edge-regular and amply regular graphs are investigated. Using linear algebra, we obtain lower bounds in certain inequalities involving the parameters of the designs. ...Some results on designs meeting the bounds are obtained. These designs are over connected regular graphs with least eigenvalue
-
2
, have the minimal number of blocks and do not appear in an earlier work. Partial classification such designs over strongly regular graphs with least eigenvalue
-
2
is given.
For graphs G and H, denote by rk+1(G;H) the minimum N such that any edge-coloring of KN by k+1 colors contains either a monochromatic G in the first k colors or a monochromatic H in the last color. ...As usual, we write r2(G;H) as r(G,H). We show that if integers s≥t≥m≥1, then rk+1(Kt,s;Km,n)≤n+(1+o(1))(s−t+1)1/tkmn1−1/t as n→∞. The upper bound is shown to be sharp up to the asymptotical sub-linear term for rk+1(K2,s;K1,n), rk+1(K3,3;K1,n), r(K2,s,K2,n) and r(K3,3,Km,n) for m≤3.
For a distance-regular graph \(\Gamma\) of diameter 3, the graph \(\Gamma_i\) can be strongly regular for \(i=2\) or 3. J.Kulen and co-authors found the parameters of a strongly regular graph ...\(\Gamma_2\) given the intersection array of the graph \(\Gamma\) (independently, the parameters were found by A.A. Makhnev and D.V.Paduchikh). In this case, \(\Gamma\) has an eigenvalue \(a_2-c_3\). In this paper, we study graphs \(\Gamma\) with strongly regular graph \(\Gamma_2\) and eigenvalue \(\theta=1\). In particular, we prove that, for a \(Q\)-polynomial graph from a series of graphs with intersection arrays \(\{2c_3+a_1+1,2c_3,c_3+a_1-c_2;1,c_2,c_3\}\), the equality \(c_3=4 (t^2+t)/(4t+4-c_2^2)\) holds. Moreover, for \(t\le 100000\), there is a unique feasible intersection array \(\{9,6,3;1,2,3\}\) corresponding to the Hamming (or Doob) graph \(H(3,4)\). In addition, we found parametrizations of intersection arrays of graphs with \(\theta_2=1\) and \(\theta_3=a_2-c_3\).
On the order of antipodal covers Wang, Jianfeng; Zhang, Wenqian; Wang, Yiqiao ...
Journal of graph theory,
February 2024, 2024-02-00, 20240201, Letnik:
105, Številka:
2
Journal Article
Recenzirano
A noncomplete graph G $G$ of diameter d $d$ is called an antipodal r $r$‐cover if its vertex set can be partitioned into the subsets (also called fibres) V
1
,
V
2
,
…
,
V
m ${V}_{1},{V}_{2},\ldots ...,{V}_{m}$ of r $r$ vertices each, in such a way that two vertices of G $G$ are at distance d $d$ if and only if they belong to the same fibre. We say that G $G$ is symmetric if for every u
∈
V
i
,
v
∈
V
j $u\in {V}_{i},v\in {V}_{j}$, there exist u
′
∈
V
i $u^{\prime} \in {V}_{i}$ such that d
(
u
,
u
′
)
=
d
(
u
,
v
)
+
d
(
v
,
u
′
) $d(u,u^{\prime} )=d(u,v)+d(v,u^{\prime} )$, where 1
≤
i
≠
j
≤
m $1\le i\ne j\le m$. In this paper, we prove that, for r
≥
2 $r\ge 2$, an antipodal r $r$‐cover which is not a cycle, has at least r
3
d
2 $r\unicode{x0230A}\frac{3d}{2}\unicode{x0230B}$ vertices provided d
≥
3 $d\ge 3$, and at least 2
r
(
d
−
1
) $2r(d-1)$ vertices provided it is symmetric. Our results extend those of Göbel and Veldman.
In the class of distance-regular graphs of diameter 3 there are 5 intersection arrays of graphs with at most 28 vertices and noninteger eigenvalue. These arrays are \(\{18,14,5;1,2,14\}\), ...\(\{18,15,9;1,1,10\}\), \(\{21,16,10;1,2,12\}\), \(\{24,21,3;1,3,18\}\), and \(\{27,20,7;1,4,21\}\). Automorphisms of graphs with intersection arrays \(\{18,15,9;1,1,10\}\) and \(\{24,21,3;1,3,18\}\) were found earlier by A.A. Makhnev and D.V. Paduchikh. In this paper, it is proved that a graph with the intersection array \(\{27,20,7;1,4,21\}\) does not exist.
PDF