Regular graphs with a complete bipartite graph as a star complement Xiaona Fanga Lihua Youa Rangwei Wua Yufei Huangb

2025-04-29 1 0 1.16MB 22 页 10玖币

侵权投诉

Regular graphs with a complete bipartite graph as a star

complement∗

Xiaona Fanga, Lihua Youa†

, Rangwei Wua, Yufei Huangb

aSchool of Mathematical Sciences, South China Normal University,

Guangzhou, 510631, P. R. China

bDepartment of Mathematics Teaching, Guangzhou Civil Aviation College,

Guangzhou, 510403, P. R. China

Abstract: Let Gbe a graph of order nand µbe an adjacency eigenvalue of Gwith multiplicity

k≥1. A star complement Hfor µin Gis an induced subgraph of Gof order n−kwith no

eigenvalue µ, and the vertex subset X=V(G−H) is called a star set for µin G. The study of

star complements and star sets provides a strong link between graph structure and linear algebra.

In this paper, we study the regular graphs with Kt,s (s≥t≥2) as a star complement for an

eigenvalue µ, especially, characterize the case of t= 3 completely, obtain some properties when

t=s, and propose some problems for further study.

Keywords: Adjacency eigenvalue; Star set; Star complement; Regular graph.

AMS classiﬁcation: 05C50

1 Introduction

Let Gbe a simple graph with vertex set V(G) = {1,2, . . . , n}= [n] and edge set E(G). The

adjacency matrix of Gis an n×nmatrix A(G)=(aij), where aij = 1 if vertex iis adjacency to

vertex j, and 0 otherwise. We use the notation i∼j(ij) to indicate that i, j are adjacent

(not-adjacent) and the notation dG(i) to indicate the degree of vertex iin G. The adjacency

eigenvalues of Gare just the eigenvalues of A(G). For more details on graph spectra, see [6].

Let µbe an eigenvalue of Gwith multiplicity k. A star set for µin Gis a subset Xof V(G)

such that |X|=kand µis not an eigenvalue of G−X, where G−Xis the subgraph of Ginduced

by X=V(G)\X. In this situation H=G−Xis called a star complement corresponding to

µ. Star sets and star complements exist for any eigenvalue of a graph, and they need not to be

unique. The basic properties of star sets are established in Chapter 7 of [7].

∗This work is supported by the National Natural Science Foundation of China (Grant No. 11971180), the

Guangdong Provincial Natural Science Foundation (Grant No. 2019A1515012052).

†Corresponding author: ylhua@scnu.edu.cn

arXiv:2210.04160v1 [math.CO] 9 Oct 2022

There is another equivalent geometric deﬁnition for star sets and star complements. Let G

be a graph with vertex set V(G) = {1, . . . , n}and adjacency matrix A. Let {e1, . . . , en}be the

standard orthonormal basis of Rn,µbe an eigenvalue of G, and Pbe the matrix which represents

the orthogonal projection of Rnonto the eigenspace E(µ) = {x∈Rn:A(G)x=µx }of Awith

respect to {e1, . . . , en}. Since E(µ) is spanned by the vectors P ej(j= 1, . . . , n), there exists

X⊆V(G) such that the vectors P ej(j∈X) form a basis for E(µ). Such a subset Xof V(G) is

called a star set for µin G. In this situation H=G−Xis called a star complement for µ.

For any graph Gof order nwith distinct eigenvalues λ1, . . . , λm, there exists a partition V(G) =

X1S···SXmsuch that Xiis a star set for eigenvalue λi(i= 1, . . . , m). Such a partition is called

astar partition of G. For any graph G, there exists at least one star partition ([10]). Each star

partition determines a basis for Rnconsisting of eigenvectors of an adjacency matrix. It provides

a strong link between graph structure and linear algebra.

There are a lot of literatures about using star complements to construct and characterize

certain graphs([1,2,3,8,12,14,16,18,19,20,21,22,23,24,25]), especially, regular graphs

with a prescribed graph such as K1,s,K1OhKq,K2,5,K2,s,K1,1,t,K1,1,1,t,sK1∪Kt,Pt(µ= 1),

Kr,r,r (µ= 1) or Kr,s +tK1(µ= 1) as a star complement were well studied in the literature.

Motivated by the above research, in this paper, we introduce the fundamental properties of the

theory of star complements in Section 2, study the regular graphs with the bipartite graph Kt,s (s≥

t≥1) as a star complement for an eigenvalue µin Section 3, completely characterize the regular

graphs with K3,s (s≥3) as a star complement for an eigenvalue µin Section 4, study some

properties of Ks,s in Section 5, and propose some problems for further research.

2 Preliminaries

In this section, we introduce some results of star sets and star complements that will be re-

quired in the sequel. The following fundamental result combines the Reconstruction Theorem ([7,

Theorem 7.4.1]) with its converse ([7, Theorem 7.4.4]).

Theorem 2.1. ([7]) Let µbe an eigenvalue of Gwith multiplicity k,Xbe a set of vertices in the

graph G. Suppose that Ghas adjacency matrix

AXBT

B C ,

where AXis the adjacency matrix of the subgraph induced by X. Then Xis a star set for µin G

if and only if µis not an eigenvalue of Cand

µI −AX=BT(µI −C)−1B. (2.1)

In this situation, E(µ)consists of the vectors

x

(µI −C)−1Bx,(2.2)

where x∈Rk.

Note that if Xis a star set for µ, then the corresponding star complement H(= G−X) has

adjacency matrix C, and (2.1) tells us that Gcan be determined by µ,Hand the H-neighbourhood

of vertices in X, where the H-neighbourhood of the vertex u∈X, denoted by NH(u), is deﬁned

as NH(u) = {v|v∼u, v ∈V(H)}.

It is usually convenient to apply (2.1) in the form

m(µ)(µI −AX) = BTm(µ)(µI −C)−1B,

where m(x) is the minimal polynomial of C. This is because m(µ)(µI −C)−1is given explicitly

as follows.

Proposition 2.2. ([8], Proposition 0.2) Let Cbe a square matrix with minimal polynomial

m(x) = xd+1 +cdxd+cd−1xd−1+··· +c1x+c0.

If µis not an eigenvalue of C, then

m(µ)(µI −C)−1=adCd+ad−1Cd−1+··· +a1C+a0I,

where ad= 1 and for 0< i ≤d,ad−i=µi+cdµi−1+cd−1µi−2+··· +cd−i+1.

In order to ﬁnd all the graphs with a prescribed star complement Hfor µ, we need to ﬁnd all

solution AX,Bfor given µand C. For any x,y∈Rq, where q=|V(H)|, let

hx,yi=xT(µI −C)−1y.(2.3)

Let bube the column of Bfor any u∈X. By Theorem 2.1, we have

Corollary 2.3. ([10], Corollary 5.1.8 ) Suppose that µis not an eigenvalue of the graph H, where

|V(H)|=q. There exists a graph Gwith a star set X={u1, u2, . . . , uk}for µsuch that G−X=H

if and only if there exist (0,1)-vectors bu1,bu2,...,bukin Rqsuch that

(1) hbu,bui=µfor all u∈X, and

(2) hbu,bvi=−1, u ∼v

0, u vfor all pairs u, v in X.

In view of the two equations in the above corollary, we have

Lemma 2.4. ([7]) Let Xbe a star set for µin G, and H=G−X.

(1) If µ6= 0, then V(H)is a dominating set for G, that is, the H-neighbourhood of any vertex in

Xare non-empty;

(2) If µ /∈ {−1,0}, then V(H)is a location-dominating set for G, that is, the H-neighbourhood of

distinct vertices in Xare distinct and non-empty.

It follows from (2) of Lemma 2.4 that there are only ﬁnitely regular graphs with a prescribed

star complement for µ /∈ {−1,0}. If µ= 0 and Xhas distinct vertices uand vwith the same

neighbourhood in G, then uand vare called duplicate vertices. If µ=−1 and Xhas distinct

vertices uand vwith the same closed neighbourhood in G, then uand vare called co-duplicate

vertices (see [11]).

Recall that if the eigenspace E(µ) is orthogonal to the all-1 vector jthen µis called a non-main

eigenvalue. From (2.2), we have the following result.

Lemma 2.5. ([8], Proposition 0.3) The eigenvalue µis a non-main eigenvalue if and only if

hbu,ji=−1for all u∈X, (2.4)

where jis the all-1 vector.

Lemma 2.6. ([10], Corollary 3.9.12) In an r-regular graph, all eigenvalues other than rare non-

main.

In the rest of this paper, we let H∼

=Kt,s (s≥t≥1), (V, W ) be a bipartition of the graph Kt,s

with V={v1, v2, . . . , vt},W={w1, w2, . . . , ws}. We say that a vertex u∈Xis of type (a, b) if it

has aneighbours in Vand bneighbours in W. Clearly (a, b)6= (0,0) and 0 ≤a≤t, 0 ≤b≤s.

Let Cbe the adjacency matrix of H, then Chas minimal polynomial m(x) = x(x2−ts).Since

µis not an eigenvalue of C, we have µ6= 0 and µ26=ts. From Proposition 2.2, we have

m(µ)(µI −C)−1=C2+µC + (µ2−ts)I. (2.5)

If µis a non-main eigenvalue of G, then by (2.4) and (2.5) we have

µ2(a+b) + µ(as +tb) = −µ(µ2−ts).(2.6)

Using (2.5) to compute hbu,bui=µ, we obtain the following equation

(µ2−ts)(a+b) + a2s+tb2+ 2abµ =µ2(µ2−ts).(2.7)

Let u, v be distinct vertices in Xof type (a, b), (c, d), respectively. Let ρuv =|NH(u)∩NH(v)|,

auv = 1 or 0 according as u∼vor uv. Using (2.5) to compute hbu,bvi=−auv, we have

(µ2−ts)ρuv +acs +bdt +µ(ad +bc) = −µ(µ2−ts)auv.(2.8)

3 Regular graphs with Kt,s as a star complement

An r-regular graph Gwith nvertices is said to be strongly regular with parameters (n, r, e, f)

if every two adjacent vertices in Ghave ecommon neighbours and every two non-adjacent vertices

have fcommon neighbours. For example, Petersen graph is strongly regular with parameters

(10,3,0,1).

For the regular graphs with the complete bipartite graph Kt,s as a star complement, the case

of t= 1 was solved by Rowlinson and Tayfeh-Rezaie in 2010 ([19]), the case of t= 2, s = 5 was

solved by Rowlinson and Jackson in 1999 ([18]), the case of t= 2, s 6= 5 was solved by Yuan,

Zhao, Liu and Chen in 2018 ([25]), and the conclusions are listed below.

Theorem 3.1. ([19]) If the r-regular graph Ghas K1,s (s > 1) as a star complement for an eigen-

value µ, then one of the following holds:

(1) µ=±2, r =s= 2 and G∼

=K2,2;

(2) µ=1

2(−1±√5), r =s= 2 and Gis a 5-cycle;

(3) µ∈N+, r =sand Gis strongly regular with parameters (µ2+ 3µ)2, µ (µ2+ 3µ+ 1) ,0, µ(µ+ 1).

Theorem 3.2. ([18,25]) Let s≥2. If the r-regular graph Ghas K2,s as a star complement for

an eigenvalue µ, then one of the following holds:

(1) µ=±3, r =s= 3 and G∼

=K3,3;

(2) 1 6=µ∈N+, r =sand Gis an r-regular graph of order (µ4+ 10µ3+ 27µ2+ 10µ)/4, where

r=µ(µ+ 1)(µ+ 4)/2.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Regulargraphswithacompletebipartitegraphasastarcomplement*XiaonaFanga,LihuaYoua,RangweiWua,YufeiHuangbaSchoolofMathematicalSciences,SouthChinaNormalUniversity,Guangzhou,510631,P.R.ChinabDepartmentofMathematicsTeaching,GuangzhouCivilAviationCollege,Guangzhou,510403,P.R.ChinaAbstract:LetGbeagraphofor...

展开>> 收起<<

Regular graphs with a complete bipartite graph as a star complement Xiaona Fanga Lihua Youa Rangwei Wua Yufei Huangb.pdf

共22页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Regular graphs with a complete bipartite graph as a star complement Xiaona Fanga Lihua Youa Rangwei Wua Yufei Huangb

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: