Probing equivalent definitions of 2-edge connected graphs
-
摘要: k-边连通图在网络研究和图论研究中有着极其重要的地位.图论中有关2-,边连通图的命题很多, 它们刻画了2-,边连通的本质.本文给出17种关于2-边连通图的等价性命题,力图从不同角度深入理解、挖掘2-边连通图的本征,并从本文定义的2种新运算出发, 提出了新的有关2-边连通图的命题,并给出这些命题相互间的等价性证明.Abstract: As known, k-edge connected graphs play an important role in the research of networks and graph theory. There are many propositions of 2-edge connected graphs nowadays, which depict the essences of 2-edge connected graphs. We present 17 equivalent propositions of 2-edge connected graphs and dig more properties of 2-edge connected graphs from different aspects of 2-edge connected graphs. Furthermore, two equivalent propositions of 2-edge connected graphs by two new operations are proposed, and then we provide the equivalent proofs between the propositions we have collected and discovered.
-
Key words:
- 2-edge connected graph /
- ear edge decomposition /
- block /
- trail /
- cycle
-
-
[1] CRUCITTI P, LATORA V, MARCHIORI M, et al. Error and attack tolerance of complex networks [J]. Physica A, 2004, 340: 388-394. doi: 10.1016/j.physa.2004.04.031 [2] KRAPIVSKY P L, REDNER S, LEYVRAZ F. Connectivity of growing random networks [J]. Phys Rev Lett, 2000, 85(21): 4629-4632. doi: 10.1103/PhysRevLett.85.4629 [3] YAO B, YANG C, YAO M, et al. Graphs as models of scale-free networks [J]. Applied Mechanics and Materials, 2013, 380-384: 2034-2037. [4] YAO B, WANG H Y, YAO M, et al. On the collapse of graphs related to scale-free networks [C]//Proceeding of the 3rd International Conference on Information Science and Technology. 2013: 738-743. [5] YAO B, LIU X, ZHANG W J, et al. Applying graph theory to the internet of things [C]//2013 IEEE International Conference on High Performance Computing and Communications and 2013 IEEE International Conference on Embedded and Ubiquitous Computing. 2013: 2354-2361. [6] WEST D B. 图论导论 [M]. 李建中, 骆吉洲, 译. 原书第2版. 北京:机械工业出版社, 2006. [7] BONDY J A, MURTY U S R. Graph Theory with Applications [M]. New York: The Macmillan Publishers, 1976. [8] 高随祥. 图论与网络流理论[M]. 北京: 高等教育出版社, 2009. [9] DIESTEL R. Graph Theory [M]. 于春林, 王涛, 王光辉, 译. 第4版. 北京:高等教育出版社, 2012.