期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

The Cycle Structure for Directed Graphs on Surfaces

The Cycle Structure for Directed Graphs on Surfaces
原文传递
导出
摘要 In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles. In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.
作者 Zhao Xiang LI
机构地区 Department of Mathematics
出处 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2015年第1期170-176,共7页 数学学报（英文版）
基金 Supported by NSFC(Grant No.10771225) Fundamental Research Funds for the Central University
关键词 Directed graph strongly connected directed cycles cycles space Directed graph, strongly connected, directed cycles, cycles space
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献1

二级参考文献22

  • 1[11]Holzmann,C.A.,Harary,F.,On the tree graph of a matroid,SIAM J.Appl.Math.,1972,22:187-193.
  • 2[12]Liu,G.Z.,On the connectivities of tree graphs,J.of Graph Theory,1988,12:453-454.
  • 3[13]Chua,L.O.,Chen,L.,On optimally sparse cycle and coboundary basis for a linear graph,IEEE Trans.Circuit Theory,1973,CT-20:495-503.
  • 4[14]Cassell,A.C.,Henderson,J.C.,Ramachandran,K.,Cycle bases of minimum measure for the structural analysis of skeletal structures by the flexibility method,Proc.Roy.Soc.London,Ser.A,1976,350(1976):61-70.
  • 5[15]Kaveh,A.,Structural Mechanics:Graph and Matrix Methods,Exeter:Research studies Press,1992,23-40.
  • 6[16]Downs,G.D.,Valerie,J.G.,Holliday,J.D.et al.,Review of ring perception algorithms for chemical graphs,J.Chem.Inf.Comput.Sci.,1989,29:172 187.
  • 7[17]Freierm,S.M.,Kierzek,R.,Jaeger,J.A.et al.,Improved free-energy parameters for predictions of RNA duplex stability,Proc.Natl.Acad.Sci.(USA),1986,83:9373-9377.
  • 8[18]Horton,J.D.,A polynomial-time algorithm to find the shortest cycle base of a graph,SIAM.J.Comput.,1987,16:359-366.
  • 9[19]Thomassen,C.,Embeddings of graphs with no short noncontractible cycles,J.of Combin.Theory,Ser.B,1990,48:155-177.
  • 10[20]Hall,P.,On representatives of subsets,London Math.Soc.,1935,10:26-30.

共引文献3

Acta Mathematica Sinica,English Series
2015年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部