Sufficient conditions for triangle-free graphs to be super-$λ'$

Document Type : Research Paper

Authors

1 Department of Mathematics, Zhongguancun Institute

2 Department of Mathematics, Beijing Jiaotong University, China

Abstract

An edge-cut $F$ of a connected graph $G$ is called a‎ ‎restricted edge-cut if $G-F$ contains no isolated vertices‎. ‎The minimum cardinality of all restricted edge-cuts‎ ‎is called the restricted edge-connectivity $λ'(G)$ of $G$‎. ‎A graph $G$ is said to be $λ'$-optimal if $λ'(G)=\xi(G)$‎, ‎where‎ ‎$\xi(G)$ is the minimum edge-degree of $G$‎. ‎A graph is said to‎ ‎be super-$λ'$ if every minimum restricted edge-cut isolates‎ ‎an edge‎.
 
‎In this paper‎, ‎first‎, ‎we provide a short proof of a previous theorem about‎ ‎the sufficient‎ ‎condition for $λ'$-optimality in triangle-free graphs‎, ‎which was given in‎ ‎[J‎. ‎Yuan ‎and‎ ‎A‎. ‎Liu‎, ‎Sufficient conditions for $λ_k$-optimality in triangle-free‎ ‎graphs‎, ‎Discrete Math‎., ‎310 (2010) 981--987]‎. ‎Second‎, ‎we generalize a known‎ ‎result about the sufficient‎ ‎condition for triangle-free graphs being super-$λ'$ which was given by‎ ‎Shang et al‎. ‎in [L‎. ‎Shang ‎and‎ ‎H. P‎. ‎Zhang‎, ‎Sufficient conditions for graphs to be $λ'$-optimal and super-$λ'$‎, Network}, 309 (2009) 3336--3345]‎.
 

Keywords

Main Subjects

References

[1] A. Esfahanian, Genralized measures of fault tolerance with application to n -cub e networks, IEEE Tran. Comput. ,
38 (1989) 1586{1591.
[2] A. Esfahanian and S. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. , 27
(1988) 195{199.
[3] A. Hellwig and L. Volkmannb, Sufficient conditions for  ′ -optimality in graphs of diameter 2, Discrete Math. , 283
(2004) 113{204.
[4] A. Hellwig and L. Volkmannb, Sufficient conditions for graphs to b e  ′ -optimal, sup er-edge-connected and maximally
edge-connected, J. Graph Theory , 48 (2005) 228{246.
[5] L. Shang and H. P. Zhang, Sufficient conditions for graphs to b e  ′ -optimal and sup er-  ′ , Networks , 309 (2009)
3336{3345.
[6] Y.-Q. Wang, Sup er restricted edge-connectivity of vertex-transitive graphs, Discrete Math. , 289 (2004) 199{205.
[7] D. B. West, Introduction to Graph Theory , Prentice Hall Inc., Upp er Saddle River, NJ, 1996.
[8] J. Yuan and A. Liu, Sufficient conditions for  k -optimality in triangle-free grapsh, Discrete Math. , 310 (2010)
981{987.
[9] J.-M. Xu and K.-L. Xu, On restricted edge-connectivity of graphs, Discrete Math. , 243 (2002) 291{298.
Transactions on Combinatorics
Volume 7, Issue 3 - Serial Number 3
September 2018
Pages 29-36

Files

History

  • Receive Date: 24 September 2017
  • Revise Date: 23 January 2018
  • Accept Date: 05 January 2018
  • Published Online: 01 September 2018

Share

How to cite

Statistics