Linear Algebra and its Applications 483(2015)
评价方案
21–29
Contents lists available at ScienceDirect
Linear Algebra and its Applications
羊肉萝卜饺子
/locate/laa
A note on connected bipartite graphs of fixed order
and size with maximal index
Miroslav Petrovića , Slobodan K.Simića ,b ,∗
a State University of Novi Pazar, Vuka Karadžića bb, 36 300 Novi Pazar, Serbia
b
Mathematical Institute, Serbian Academy of Sciences and Arts, P.O. Box 367,
11001 Belgrade, Serbia a r t i c l e i n f o a b s t r a c t
Article history:Received 20 February 2015Accepted 8 May 2015A vailable online 2 June 2015Submitted by S. Friedland
MSC:
05C50
Keywords:
Adjacency matrix
Graph spectrum
Largest eigenvalue
Double nested graphs
Bipartite chain graphs
降频
In this paper the unique graph with maximal index (i.e. the
largest eigenvalue of the adjacency matrix) is identified among
all connected bipartite graphs of order n and size n +k , under
the assumption that k ≥0and n ≥k +5.
©2015 Elvier Inc. All rights rerved.1. Introduction
Let G =(V, E )be a simple graph with vertex t V and edge t E . Its order is |V |, denoted
by n , and its size is |E |, denoted by m . Let A =A (G )be the (0, 1)-adjacency matrix of G . Since A is symmetric, its eigenvalues are real, and also called the eigenvalues *Corresponding author.
E-mail address:petrovic@kg.ac.rs (M.Petrović), sksimic@mi.sanu.ac.rs (S.K.Simić).
/10.1016/j.laa.2015.05.013
0024-3795/©2015 Elvier Inc. All rights rerved.
22M.Petrović,S.K.Simić/Linear Algebra and its Applications 483(2015)21–29of G . The largest eigenvalue of G is denoted by ρ(G ), and also called the spectral radius , or index for short. For the least eigenvalue of G we write λ(G ). If clear from the context, graph names are usually omitted. For all other terminology and notation the reader is referred to [9].
In [3], Bell et al. studied connected graphs who least eigenvalue is minimal among graphs of prescribed order and size. Their main structural result reads:
Theorem 1. Let G be a connected graph who least eigenvalue is minimal among the connected graphs of order n and size m (n −1 ≤m < n
2 ). Then G is
(i)a bipartite graph, or
(ii)a join (or complete product) of two nested split graphs (not both totally disconnected).
Recall, a graph is called a nested split graph (or NSG for short) if its vertices can be ordered so that jq ∈E (G )implies ip ∈E (G )whenever i ≤j and p ≤q . Nested split graphs are in fact threshold graphs, so {2K 2, P 4, C 4}-free graphs.
In [4]and [11], further steps have been made in investigating graphs G for which the least eigenvalue λ(G )is minimal among connected graphs of prescribed order and size. Namely, the structure of connected bipartite graphs of prescribed order and size with maximal index is studied, and thereby the structure of tho with minimal least eigen-value. The relevance of the investigations stems from Theorem 1(i), and well-known fact that λ(G ) =−ρ(G )for any bipartite graph G (e, e.g. [9], p. 56). Before we state the main result from [4]and [11]we first introduce a further class of bipartite graphs, namely double nested graphs (also called bipartite chain graphs , e for example [5]). As is well known from the literature, the graphs are {2K 2, C 3, C 5}-free graphs (e, for example, [2]).
那一段难忘的时光Let G be a connected bipartite graph with colour class U and V . We say that G is double nested graph (or DNG for short) if there exist partitions
黄豆排骨汤的做法U =U 1˙∪U 2˙∪...˙∪U h and V =V 1˙∪
V 2˙∪...˙∪V h ,such that the neighbourhood of each vertex in U 1is V 1˙∪
泡馍的做法
V 2˙∪...˙∪V h , the neighbourhood of each vertex in U 2is V 1˙∪
V 2˙∪...˙∪V h −1, and so on. If |U i | =m i and |V i | =n i (i =1, 2, ..., h ) then we write
G =D (m 1,m 2,...,m h ;n 1,n 2,...,n h ).(1)
Such a graph is depicted in Fig.1. Any fat circle corresponds to a co-clique of an ap-propriate size; any line between two fat circles means that each vertex in one fat circle is adjacent to all vertices in the other fat circle.
For the double nested graphs the next two relations hold:
n (G )=m 1+···+m h +n 1+···+n h ,
(2)m (G )=m 1(n 1+···+n h )+m 2(n 1+···+n h −1)+···+m h n 1.(3)
M.Petrović,S.K.Simić/Linear Algebra and its Applications483(2015)21–2923 Fig.1.The structure of D(m1,m2,...,m h;n1,n2,...,n h).
Fig.2.The graph D(1,1;k+2,n−k−4).
The following result is taken from[11].
Theorem2.Let G be a graph for whichρ(G)is maximal among all connected bipartite graphs of order n and size n+k,with k≥0and n≥k+5.Then G is double nested graph(1)and the following hold:
10h>1,
20exactly one of the parameters m1and n1is equal to1,
30if h=2then G=D(1,1;k+2,n−k−4)(e Fig.2),
40h=3.
24M.Petrović,S.K.Simić/Linear Algebra and its Applications483(2015)21–29
In this paper we prove that the graph G=D(1,1;k+2,n−k−4)is the unique graph with maximal index among connected bipartite graphs of order n and size n+k(with k≥0and n≥k+5).We also determine its index,which features as the best possible upper bound for the index of graphs in the obrved class.
2.The main result
Wefirst prove the following auxiliary result:
Lemma1.Let m2,m3,...,m h,n1,n2,...,n h−1(h≥3)and k be natural numbers with n1≥2.If
k+1≥m2(n1+···+n h−1−1)+···+m h−1(n1+n2−1)+m h(n1−1)(4) then
k+3≥(m2+m3+···+m h)+(n1+n2+···+n h−1).(5)
Proof.Let M i,j=
j
s=i m s and N i,j=
j
市场总监职责
s=i
n s(i≤j).Rewriting(4)as
k+1≥m2(N1,h−1−1)+m3(N1,h−2−1)+···+m h(N1,1−1),
and having in view that ab≥a+b−1for a,b≥1,we obtain that
k+1≥M2,h+N1,h−1+N1,h−2+···+N1,1−2(h−1).
In view of assumptions,we obtain for h=3:
k+1≥M2,3+N1,2+n1−4,
whence
k+3≥M2,3+N1,2+n1−2≥M2,3+N1,2.
For h≥4we have
k+1≥M2,h+N1,h−1+(h−2)n1+N2,h−2+···+N2,2−2(h−1) >M2,h+N1,h−1+(h−2)(n1−2)−2,
whence
k+3>M2,h+N1,h−1,
as required by(5).
This completes the proof.2
M.Petrović,S.K.Simić/Linear Algebra and its Applications483(2015)21–2925
Let X=(x1,x2,...,x n)T be a column vector in R n,and G a double nested graph (e(1))on vertices v1,v2,...,v n.Then X can be considered as a function defined on the vertex t of G,and which maps a vertex v i to X(v i),also denoted by x v
i
,or x i for short.We say that x i is the weight of the vertex v i obtained from X.One canfind that λis an eigenvalue of G corresponding to the eigenvector X if and only if X is non-zero and
λx i=
v i v j∈E(G)
x j for each i=1,2,...,n.(6)
Eqs.(6)are called(λ,X)-eigenequations of G.
For a connected double nested graph G of order n and size m,letρ=ρ(G)be its index.Since A=A(G)is a nonnegative and irreducible matrix,an eigenvec-tor X=(x1,x2,...,x n)T corresponding toρcan be taken to be positive.By the (λ,X)-eigenequations(6)we have that all vertices within the ts U i and V i forfixed i (1≤i≤h)have the same weights.Let x u=a i if u∈U i,and let x v=b i if v∈V i (i=1,2,...,h).
In the next lemma some relations on bounding the b i’s(similar relations for a i’s are obtained by interchanging the values of the m i’s and n i’s)are given.The next lemma is taken from[2](e Lemma3.4).Now it is restated to some extent to fulfill our further of needs.
Lemma2.Let G=D(m1,m2,...,m h;n1,n2,...,n h),and letρbe the index of G.Fur-thermore,let
αi=m1+···+m h+1−i(i=1,2,...,h)
βi=m2n h+m3(n h+n h−1)+···+m h+1−i(n h+···+n i+1)(i=1,2,...,h−1)βh=0.
Then for any i=1,2,...,h we have
b i≤a1
ρ
对香烟αi−
m1
ρ
βi
.
Theorem3.The graph G=D(1,1;k+2,n−k−4)(e Fig.2)is the unique graph with maximal index among all connected bipartite graphs of order n and size m,with k≥0 and n≥k+5.
Proof.Let G be a graph for which the largest eigenvalueρ=ρ(G)is maximal among all connected bipartite graphs of order n and size n+k,with k≥0and n≥k+5.Then, by Theorem2,G is double nested g
raph
