极大3等周边连通图的充分条件

doi:10.3976/j.issn.1002-4026.2016.04.015

Abstract

Abstract:

k-isoperimetric edge connectivity is a more reliable network reliability index than edge connectivity. k-isoperimetric edge connectivity of a connected graph G is defined as γk(G)=min{［X,X-］:X $\100dpi \inline \subseteq$ V(G),X≥k,X-≥k},where X-=V(G)＼X. Let βk(G)=min{［X,X-］:X $\100dpi \inline \subseteq$ V(G),X=k}. A graph G is maximally k-isoperimetric edge connected if γk(G)=βk(G). Let G be a connected graph of at least order 6. We prove that for any pair of nonadjacent vertices u,v in G, N(u)∩N(v)≥2 holds when u and v are not on a triangle. If N(u)∩N(v)≥5 holds for u or v on a triangle, then G is maximally 3isoperimetric edge connected.

Key words: maximally k-isoperimetric edge connected graph, k-isoperimetric edge connectivity, neighborhood, interconnection networks

CLC Number:

O157.6

XU Zi-jun,ZHANG Lei. Sufficient conditions of a maximally 3-isoperimetric edge connected graph[J].SHANDONG SCIENCE, 2016, 29(4): 75-79.

[1]	LIU Haibin, WANG Jubo, BA Bosheng, WANG Ruixin. A numerical comparison of methods for solving the gate allocation problem based on robustness simulation [J]. Shandong Science, 2024, 37(2): 104-116.
[2]	ZHANG Yiguo, QU Yunchao, YIN Haodong, WU Jianjun. Route optimization for emergency evacuation vehicles in case of rail station closure [J]. Shandong Science, 2023, 36(4): 80-88.
[3]	CHEN Qing, XU Xiaoming. Electric vehicle pickup and delivery based on link recharging and time windows [J]. Shandong Science, 2023, 36(3): 78-89.
[4]	FAN Xian,XU Xiao-ming,QIAN Cheng. Optimization of shunting operation plan of electrical multiple unit depots [J]. Shandong Science, 2022, 35(2): 96-105.
[5]	WANG Kai, CAO Bang-Hua, SUN Chao, CHEN Jian-Jian, TAI Xiu-Guo, YANG Zhen-Ya. Spatial structure analysis of artificial forest of Pinus tabulaeformis,Robinia pseudoacaia and Platycladus orientalis from Lushan National Forest Park [J]. J4, 2014, 27(3): 39-43.
[6]	GAO Jing-Zhen, LYU Min. Neighborhood conditions for maximally and super-local-edge-connected digraphs [J]. J4, 2012, 25(5): 1-5.
[7]	GAO Jing-Zhen, SHAO Guang-Feng. Neighborhood conditions of maximally local edge connected and super local edge connected bipartite digraphs [J]. J4, 2012, 25(2): 1-7.
[8]	CAO Meng-Meng, SUN Lei. Several N(p,q) label issues of a graph [J]. J4, 2011, 24(4): 69-72.
[9]	GAO Jing-Zhen, MA Yu. Sufficient conditions of a λ₄- optimal and super -λ₄ graph [J]. J4, 2011, 24(1): 61-64.
[10]	DONG Wei. An improved variable neighborhood search based solution to the k-card inality tree problem [J]. J4, 2011, 24(1): 93-96.

Sufficient conditions of a maximally 3-isoperimetric edge connected graph

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Metrics

Comments

Recommended 0