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.
A graph is called an edge-regular graph with parameters (
n
,
k
,
a
) if it is a
k
-regular graph with
n
vertices and any two adjacent vertices have
a
common neighbours. A quasi-strongly regular ...graph with parameters
(
n
,
k
,
a
;
c
1
,
c
2
)
, denoted by QSRG
(
n
,
k
,
a
;
c
1
,
c
2
)
, is an edge-regular graph with parameters (
n
,
k
,
a
) in which any two non-adjacent vertices have
c
1
or
c
2
common neighbours. A quasi-strongly regular graph is called a strictly quasi-strongly regular graph if it is neither a strongly regular graph nor a Deza graph. The purpose of our research is to complete the structural characterization of strictly QSRG
(
n
,
k
,
a
;
k
-
2
,
c
2
)
. In an earlier paper, we characterised QSRG
(
n
,
k
,
a
;
k
-
2
,
c
2
)
satisfying
a
<
k
-
5
and
l
1
>
2
, where
l
1
is the number of vertices with
k
-
2
common neighbours with a given vertex. In the present paper, we investigate the structural characterization of strictly QSRG
(
n
,
k
,
a
;
k
-
2
,
c
2
)
satisfying
a
≥
k
-
5
.
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.
Quasi-strongly regular graphs are a combinatorial generalization of strongly regular graphs. 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 any two adjacent vertices have a common neighbours, any two non-adjacent 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 of grade 2 is neither a strongly regular graph nor a Deza graph, then it is called a strictly quasi-strongly regular graph. In this paper, we characterize strictly quasi-strongly regular graphs with parameters satisfying c1=k−1.
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.
