Some inequalities on the skew-spectral radii of oriented graphs

Xu

Description

Let G be a simple graph and G σ be an oriented graph obtained from G by assigning a direction to each edge of G . The adjacency matrix of G is A ( G ) and the skew-adjacency matrix of G σ is S ( G σ ) . The adjacency spectral radius ρ ( G ) of G and the skew-spectral radius ϱ ( G σ ) of G σ are defined as the spectral radius of A ( G ) and S ( G σ ) respectively. In this paper, we firstly establish a relation between ϱ ( G σ ) and ρ ( G ) . Also, we give some results on the skew-spectral radii of G σ and its oriented subgraphs. As an application of these results, we obtain a sharp upper bound of the skew-spectral radius of an oriented unicyclic graph. MSC: 05C50, 15A18.

Sujets

• Directed graph
• Pseudoforest

Informations

• Publié par: biomed
• Publié le: 01 janvier 2012
• Nombre de lectures: 10
• Langue: English

Extrait

XuJournalofInequalitiesandApplications2012,2012:211
http://www.journalofinequalitiesandapplications.com/content/2012/1/211
RESEARCH OpenAccess
Someinequalitiesontheskew-spectralradii
oforientedgraphs
*Guang-HuiXu
*Correspondence:
[e-mail] Abstract
DepartmentofApplied σLetGbeasimplegraphandG beanorientedgraphobtainedfromGbyassigningaMathematics,ZhejiangA&F
University,Hangzhou,311300, directiontoeachedgeofG.TheadjacencymatrixofGisA(G)andtheskew-adjacency
σ σChina matrixofG isS(G ).Theadjacencyspectralradius ρ(G)ofGandtheskew-spectral
σ σ σradius (G )ofG aredefinedasthespectralradiusofA(G)andS(G )respectively.
σInthispaper,wefirstlyestablisharelationbetween (G )and ρ(G).Also,wegive
σsomeresultsontheskew-spectralradiiofG anditsorientedsubgraphs.Asan
applicationoftheseresults,weobtainasharpupperboundoftheskew-spectral
radiusofanorientedunicyclicgraph.
MSC: 05C50;15A18
Keywords: orientedgraph;skew-adjacencymatrix;skew-spectralradius;unicyclic
graph
1 Introduction
In this paper, i will always denote an imaginary unit. The identity matrix is denoted by I
Tand the transpose of the matrix A by A .Let G be a simple graph with n vertices. The
adjacency matrix A=A(G) is the symmetric matrix [a ] ,where a =a =if vv isjk n×n jk kj j k
an edge of G,otherwise a =a =.Wecall det(λI –A)the characteristic polynomial ofjk kj
G,denotedby P(G;λ). The adjacency spectrum S (G)of G is defined as the spectrum ofp
A(G).SinceAissymmetric,itseigenvalues λ (G),λ (G),...,λ (G)arereal,andweassume  n
that λ (G) ≥ λ (G)≥···≥ λ (G).Wecall ρ(G)= λ (G)theadjacencyspectralradiusofG.  n 
σLet G be a simple graph with an orientation σ, which assigns to each edge of G a
σ σdirection so that G becomes a directed graph. The skew-adjacency matrix S = S(G )
is the real skew-symmetric matrix [s ] ,where s =and s =–if(v,v)isanarcjk n×n jk kj j k
σof G ,otherwise s = s =. We call det(λI – S)the skew-characteristic polynomialjk kj
σ σ σ σof G ,denotedby φ(G ;λ). The skew spectrum S (G )of G is defined as the spec-p
σtrum of S(G ).Since S is skew-symmetric, its eigenvalues are purely imaginary numbers
σ σ σ σ σ σλ (G )i,λ (G )i,...,λ (G )i.Also,weassumethat λ (G ) ≥ λ (G )≥···≥ λ (G )and  n   n
σ σ σcall (G )= λ (G )theskew-spectralradiusofG .
Inthispaper,wewilldenotebyD(G)thesetofalltheorientedgraphsobtainedfromGby
givinganarbitraryorientationtoeachedge.Also,wereferto[–]formoreterminologies
andnotationsnotdefinedhere.
Unlike the adjacency matrix of a graph, there is little research on the skew-adjacency
σmatrixS(G ),exceptthatintoenumerationofperfectmatchingsofagraph.Asearlyasin
, Tutte
[]derivedhisfamouscharacterizationofthegraphswithnoperfectmatch© 2012 Xu; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons
Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any
medium,providedtheoriginalworkisproperlycited.XuJournalofInequalitiesandApplications2012,2012:211 Page2of13
http://www.journalofinequalitiesandapplications.com/content/2012/1/211
ings. Tutte’s result motivates a lot of work on the matchings polynomial and
enumerating perfect matchings of graphs in terms of its skew-adjacency matrix; see, for example,
[–]andreferencestherein.
Recently, many researchers have paid a great deal of attention to the spectral
properties of skew-symmetric matrices in terms of oriented graphs. IMA-ISU research group
on minimum rank [] studied the minimum rank of skew-symmetric matrices. In ,
Shader and So [] investigated the spectra of the skew-adjacency matrix of an oriented
graph. And in , Adiga et al. [] discussed the properties of the skew energy of an
oriented graph. In the papers []and[], all the coefficients of the skew-characteristic
σpolynomialofG intermsofG wereinterpreted.
The motivation of this paper is to study more carefully the skew spectra of oriented
σgraphs.InSection,wefirstlyestablisharelationbetween (G )and ρ(G).InSection,
σwegivesomeresultsontheskew-spectralradiiofG anditsorientedsubgraphs.Finally,
inSection,wegiveanapplicationofthepreviousresults-toobtainasharpupperbound
oftheskew-spectralradiusofanorientedunicyclicgraph.
σ2 Arelationbetweenρ(G)and(G )
σItisinterestingtodiscusstherelationsbetween ρ(G)and (G ).LetGbeasimplegraph.
WedenotedbyN(v)theneighborhoodofthevertexvinG,byG–ethesubgraphobtained
from G by deleting the edge e and by G–v the subgraph obtained from G by removing
the vertex v together with all edges incident to it. A walk W of length k from u to v in G
isasequenceof k+ verticesstartingat u andending at v suchthatconsecutivevertices
are adjacent. If all vertices in a walk are distinct, then such a walk is called a path of G,
denotedby P.Let P=v v ···v beapathwith k ≥.Then P togetherwiththeedge v v  k k 
iscalledacycleofG,denotedbyC.
σ σLet G ∈D(G)and S(G )beitsskew-adjacencymatrix.Let W = u u ···u u be a  k k+
σ σwalk of G (we often call it a (k+)-walk).Thesignof W in G ,denotedby sgn(W ), is
definedby
s s ···s s .  k–,k k,k+
¯LetW =u u ···u u bethewalkbyinvertingtheorderoftheverticesalongthewalkW.k+ k  
Thenonecanfindthat
⎧
⎨ σ –sgn(W ), ifk isodd;
σ¯sgn W =
σ⎩sgn(W ), ifk iseven.
Obviously, for an even closed walk (that is to say, u =u ), we can simply refer to it ask+ 
a positive (or negative) even closed walk according to its sign, regardless of the order of
itsvertices.Similarly,wecandefineapositive(ornegative)evencycle.Moreover,aneven
σ σ kcycleC withkverticesissaidtobeorienteduniformlyifitssigninG issgn(C )=(–) .k k
Notethatintermsofdefiningwalks,paths,cyclesetc.,wefocusonlyontheunderlying
undirectedgraph.Andtheirsignsarebasedontheorientedgraph.
σForG ∈D(G),onereversestheorientationsofallthearcsincidenttoaparticularvertex
σ σ τ σofG .WecallsuchanoperationareversalofG .LetG bethedigraphobtainedfromGXuJournalofInequalitiesandApplications2012,2012:211 Page3of13
http://www.journalofinequalitiesandapplications.com/content/2012/1/211
σ τbydoingsomereversals.ThenG andG aresaidtobequasi-isomorphicanddenotedby
σ τ σ τ σ τG G .Forexample,ifT isatreeandT ,T ∈D(T),thenwealwayshaveT T .
Onquasi-isomorphicorientedgraphs,Adigaetal.[]obtainedthefollowingresult.
σ τ σ σLemma.([]) LetG ∈D(G) and G G .Thentheskew-adjacencymatricesS(G )
τandS(G )areorthogonallysimilar.Andtherefore,
σ τ
S G =S G .p p
Fororientedbipartitegraphs,wehave
Lemma . Let G=(U,V;E) be a bipartite graph and |U| = m, |V| = n. The adjacency
matrixofGis

 X
A(G)= .
TX 
σ σLet G ∈D(G) and each even cycle of G be oriented uniformly. Then G D, where D ∈
D(G)anditsskew-adjacencymatrixis

 X
S(D)= .
T–X 
Proof Firstly, we will prove that each even closed walk of G is oriented uniformly in
σ σ kG too. That is to say, for an arbitrary closed k-walk of G,itssignin G is (–) .Let
W =u u ···u u beaclosedk-walkofG.Wemayassumetheclosedk-walkisexactly  k 
constitutedbythecycles(orclosed-walks)C withk vertices(j=,,...,r).Hence,j j
k +k +···+k k  rsgn(W)=(–) =(–) .
Now,toprovethelemma,wecanconsiderthefollowingtwocases.
∼Case.G K ;= mn
Letu ∈U,v ∈V.Obviously,wecantakesomereversalstoobtainaneworientedgraph 
τ τ τG suchthatallthearcs (u ,v),(u ,v ) ∈G (j=,,...,n, l=,,...,m).Now,if G D, j l 
τthen there exists an arc (v ,u ) ∈G ,where u ∈U and v ∈V. Thus, for the cycle C =p q q p 
σ τ u v u v u,wehave sgn(C )= sgn(C )=– =(–) . Contradicting the condition of this  q p   
σ τ σ∼lemmathateachevencycleofG isorienteduniformlyinG ,G = D,andthenG D.
Case.GK ;mn
Without loss of generality, we may assume G is connec