Two results of the compact graph and its applications

Expand
  • 1.College of Mathematics, Inner Mongolia University for Nationalities, Tongliao 028043, Inner Mongolia, China

Received date: 2014-10-08

  Online published: 2015-12-15

Abstract

Doubly stochastic matrix has many important applications, the family of compact graphs can be seen as the generalization of the famous Birkhoff theorem which is about doubly stochastic matrix,  and is of important research value. Determine whether a graph is a compact graph is a difficult problem,  at present there are only few compact graphs known. This paper gives two important results: the graph constructed by any compact graph combining some isolated points is a
compact graph; the graph constructed by adding one pendant edge to each vertex of any compact graph is also a compact graph. By these two results,  we can construct an infinite number of compact graph family from already known compact graph.

Cite this article

Siqinbate, WANG Jingyu . Two results of the compact graph and its applications[J]. Operations Research Transactions, 2015 , 19(4) : 72 -82 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.04.007

References

柳柏濂. 组合矩阵论 [M].北京: 科学出版社, 2005: 102-125.


 Tinh\"{o}fer G. Gragh isomorphism and theorems of Birkhoff type [J].  Computing, 1986, 36: 285-300.
 Birkhoff G. Tres observaciones sobre el algebra lineal [J]. Universidad Nacional de Tucum\`{a}n Revista, Serie  A, 1946,  5: 147-150.

 Brualdi A R. Some application of doubly stochastic matrices [J]. Linear Algebra Application, 1988,  107: 77-100.

 Godsil D C. Compact graphs and equitable partitions [J]. Linear Algebra Application, 1997, 225: 259-266.

 张秀平. 关于紧图超紧图的几个结果 [J]. {\it 北京师范大学学报(自然科学版), 1999,  35(1): 16-21.

 张秀平. 准补图的紧性和超紧性 [J].  北京师范大学学报(自然科学版), 1999,  35(3): 316-319.

 张秀平. 关于(m, k)图及其准补图的紧性和超紧性的补充结果 [J]. 北京师范大学学报(自然科学版), 2000,  36(5): 569-573.

 陆伟成. 紧图与超紧图的一些理论 [J].  科学技术与工程, 2011,  11(11): 2399-2403.

 张宣昊, 陆伟成. 一种构造紧图的方法 [J].  科学技术与工程, 2011,  11(26): 6249-6252.

 
Outlines

/