Edge connectivity and super edge-connectivity of jump graphs

被引:2
作者
Chen, Xing [1 ,2 ]
Liu, Juan [3 ]
Xie, Dongyang [4 ]
Meng, Jixiang [2 ]
机构
[1] Xinjiang Inst Engn, Urumqi 830091, Xinjiang, Peoples R China
[2] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
[3] Xinjiang Normal Univ, Coll Math Sci, Urumqi 830054, Xinjiang, Peoples R China
[4] State Grid Changji Elect Power Supply Co, Changji 831100, Xinjiang, Peoples R China
关键词
Line graph; Jump graph; Complement; Super connected; Super edge connected;
D O I
10.1080/02522667.2015.1103062
中图分类号
G25 [图书馆学、图书馆事业]; G35 [情报学、情报工作];
学科分类号
1205 ; 120501 ;
摘要
For a graph G, let (G) over bar and L(G) denote the complement graph and the line graph of G, and let (G) over bar denote the jump graph of G. It is well-known that (G) (G) (G). A graph G is called maximally edge connected if G has edge connectivity of its minimum degree and is called super-(edge-)connected if for every minimum vertex(edge) cut S of G, G - S has isolated vertices. In this paper, we apply previous results of edge-connectivity and super-connectivity and super-edge-connectivity to give the following four results on jump graphs: (1) Characterization of the graph G having (J (G)) = 2; (2) If J(G) is connected, then J(G) is maximally edge connected; (3) Characterization of the graph G whose J(G) is super edge connected but not super-connected; (4) Give a sufficient condition for J(G) is super edge connected.
引用
收藏
页码:233 / 246
页数:14
相关论文
共 15 条
[1]  
Bauer D., 1981, THEORY APPL GRAPHS, P45
[3]   SYNTHESIS OF RELIABLE NETWORKS - A SURVEY [J].
BOESCH, FT .
IEEE TRANSACTIONS ON RELIABILITY, 1986, 35 (03) :240-246
[4]  
Bondy JA., 1976, GRADUATE TEXTS MATH
[5]   Subgraph distances in graphs defined by edge transfers [J].
Chartrand, G ;
Hevia, H ;
Jarrett, EB ;
Schultz, M .
DISCRETE MATHEMATICS, 1997, 170 (1-3) :63-79
[6]   A GRAPH-THEORETIC APPROACH TO A COMMUNICATIONS PROBLEM [J].
CHARTRAND, G .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1966, 14 (04) :778-&
[7]   ON SUPER-EDGE-CONNECTED DIGRAPHS AND BIPARTITE DIGRAPHS [J].
FIOL, MA .
JOURNAL OF GRAPH THEORY, 1992, 16 (06) :545-555
[8]   Maximally edge-connected and vertex-connected graphs and digraphs: A survey [J].
Hellwig, Angelika ;
Volkmann, Lutz .
DISCRETE MATHEMATICS, 2008, 308 (15) :3265-3296
[9]  
Kel'mans A. K., 1973, Theory of Probability and Its Applications, V17, P243, DOI 10.1137/1117029
[10]  
Meng J., 2001, GRAPH THEORY NOTES N, VXL, P12