文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Signed degree sets in signed bipartite graphs
侵权投诉

Signed degree sets in signed bipartite graphs

A signed bipartite graph G(U, V) is a bipartite graph in which each edge is assigned a positive or a negative sign. The signed degree of a vertex x in G(U, V) is the number of positive edges incident with x less the number of negative edges incident with x

6

2

ep

S

7

]

O

C

.

th

a

m

[

2

v

2

2

1

9

6

/

tha

m

:v

i

Xr

aSigneddegreesetsinsignedbipartitegraphsS.Pirzada1,T.A.Naikoo2andF.A.Dar3DepartmentofMathematics,UniversityofKashmir,Srinagar-190006,India1Email:sdpirzada@yahoo.co.in2Email:tariqnaikoo@redi mail.com3Email:sfarooqdar@yahoo.co.inAMSClassi cation:05CAbstractAsignedbipartitegraphG(U,V)isabipartitegraphinwhicheachedgeisassignedapositiveoranegativesign.ThesigneddegreeofavertexxinG(U,V)isthenumberofpositiveedgesincidentwithxlessthenumberofnegativeedgesincidentwithx.ThesetSofdistinctsigneddegreesoftheverticesofG(U,V)iscalleditssigneddegreeset.Inthispaper,weprovethateverysetofintegersisthesigneddegreesetofsomeconnectedsignedbipartitegraph.1.IntroductionAsignedgraphisagraphinwhicheachedgeisassignedapositiveoranegativesign.TheconceptofsignedgraphsisgivenbyHarary[3].LetGbeasignedgraphwithvertexsetV={v1,v2,...,vn}.ThesigneddegreeofavertexviinGisdenotedbysdeg(vi)(orsimplyd+ nandd+bydi)andisde nedasdi=i-di,where1≤i≤i(d i)isthenumberofpositive(negative)edgesincidentwithvi.Asigneddegreesequenceσ=[d1,d2,...,dn]ofasignedgraphGisformedbylistingthevertexsigneddegreesinnon-increasingorder.Anintegralsequenceiss-graphicalifitisthesigneddegreesequenceofasignedgraph.Also,anon-zero nsequenceσ=[d1,d2,...,dn]isastandardsequenceifσ

isnon-increasing,i=1diiseven,d1>0,each|di|<n,and|d1|≥|dn|.Thefollowingresult[1],givesanecessaryandsu cientconditionforanintegralsequencetobes-graphical,whichissimilartoHakimi’sresultfordegreesequencesingraphs[2].

Theorem1.1.Astandardintegralsequenceσ=[d1,d2,...,dn]iss-graphicalifandonlyif

1

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email