Geodesic
A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 537-545.

Voir la notice de l'article provenant de la source Library of Science

For a subset S of edges in a connected graph G, S is a k-restricted edge cut if G − S is disconnected and every component of G − S has at least k vertices. The k-restricted edge connectivity of G, denoted by λ_k (G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξ_k(G) = min{ | [ X , X ] | : |X| = k, G[X] is connected }, where X = V (G) \ X. A graph G is super k-restricted edge connected if every minimum k-restricted edge cut of G isolates a component of order exactly k. Let k be a positive integer and let G be a graph of order ν≥ 2k. In this paper, we show that if | N( u ) ∪ N( v ) | ≥ k +1 for all pairs u, v of nonadjacent vertices and ξ_k (G) ≤ ν/2+k, then G is super k-restricted edge connected.
Keywords: graph, neighborhood, k -restricted edge connectivity, super k -restricted edge connected graph 
@article{DMGT_2017_37_3_a2,
     author = {Wang, Shiying and Wang, Meiyu and Zhang, Lei},
     title = {A {Sufficient} {Condition} for {Graphs} to {Be} {Super} {k-Restricted} {Edge} {Connected}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {537--545},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a2/}
}
TY  - JOUR
AU  - Wang, Shiying
AU  - Wang, Meiyu
AU  - Zhang, Lei
TI  - A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 537
EP  - 545
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a2/
LA  - en
ID  - DMGT_2017_37_3_a2
ER  - 
%0 Journal Article
%A Wang, Shiying
%A Wang, Meiyu
%A Zhang, Lei
%T A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 537-545
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a2/
%G en
%F DMGT_2017_37_3_a2
Wang, Shiying; Wang, Meiyu; Zhang, Lei. A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 537-545. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a2/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (New York, Springer, 2008).

[2] C. Balbuena, P. García-Vázquez and X. Marcote, Sufficient conditions for λ′-optimality in graphs with girth g, J. Graph Theory 52 (2006) 73–86. doi:10.1002/jgt.20150

[3] N.-W. Chang, C.-Y. Tsai and S.-Y. Hsieh, On 3 -extra connectivity and 3 -extra edge connectivity of folded hypercubes, IEEE Trans. Comput. 63 (2014) 1594–1600. doi:10.1109/TC.2013.10

[4] A.-H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. doi:10.1016/0020-0190(88)90025-7

[5] J. Fàbrega and M.A. Fiol, Extraconnectivity of graphs with large girth, Discrete Math. 127 (1994) 163–170. doi:10.1016/0012-365X(92)00475-7

[6] Q. Liu, X. Huang and Z. Zhang, Optimally restricted edge connected elementary Harary graphs, Theoret. Comput. Sci. 497 (2013) 131–138. doi:10.1016/j.tcs.2011.12.015

[7] J. Meng, Optimally super-edge-connected transitive graphs, Discrete Math. 260 (2003) 239–248. doi:10.1016/S0012-365X(02)00675-1

[8] J. Meng and Y. Ji, On a kind of restricted edge connectivity of graphs, Discrete Appl. Math. 117 (2002) 183–193. doi:10.1016/S0166-218X(00)00337-1

[9] L. Shang and H. Zhang, Super restricted edge-connectivity of graphs with diameter 2, Discrete Appl. Math. 161 (2013) 445–451. doi:10.1016/j.dam.2012.08.030

[10] M. Wang and Q. Li, Conditional edge connectivity properties, reliability comparisons and transitivity of graphs, Discrete Math. 258 (2002) 205–214. doi:10.1016/S0012-365X(02)00299-6

[11] S. Wang, L. Zhang and S. Lin, A neighborhood condition for graphs to be maximally k-restricted edge connected, Inform. Process. Lett. 112 (2012) 95–97. doi:10.1016/j.ipl.2011.10.012

[12] S. Wang, J. Li, L. Wu and S. Lin, Neighborhood conditions for graphs to be super restricted edge connected, Networks 56 (2010) 11–19. doi:10.1002/net.20343

[13] S. Wang and L. Zhang, Sufficient conditions for k-restricted edge connected graphs, Theoret. Comput. Sci. 557 (2014) 66–75. doi:10.1016/j.tcs.2014.08.018

[14] S. Wang, S. Lin and C. Li, Sufficient conditions for super k-restricted edge connectivity in graphs of diameter 2, Discrete Math. 309 (2009) 908–919. doi:10.1016/j.disc.2008.01.037

[15] M. Zhang, J. Meng, W. Yang and Y. Tian, Reliability analysis of bijective connection networks in terms of the extra edge-connectivity, Inform. Sci. 279 (2014) 374–382. doi:10.1016/j.ins.2014.03.125