Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Super Restricted Edge Connectivity of Half Vertex Transitive Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Let X =  (V, E) be a connected graph. Call X super restricted edge connected in short, sup-λ′, if F is a minimum edge set of X such that X − F is disconnected and every component of X − F has at least two vertices, then F is the set of edges adjacent to a certain edge with minimum edge degree in X. A bipartite graph is said to be half vertex transitive if its automorphism group is transitive on the sets of its bipartition. In this article, we show that every connected half vertex transitive graph X with n =  |V(X)| ≥  4 and \({X \ncong K_{1,n-1}}\) is λ′-optimal. By studying the λ′-superatoms of X, we characterize sup-λ′ connected half vertex transitive graphs. As a corollary, sup-λ′ connected Bi-Cayley graphs are also characterized.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ball M.O.: Complexity of network reliability computation. Networks 10, 153–165 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bauer D., Boesch F., Suffel C., Tindell R.: Combinatorial optimization problems in the analysis and design of probabilistic networks. Networks 15, 257–271 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bondy J.A., Murty U.S.R.: Graph Theory with Applications. Macmillan, London (1976)

    MATH  Google Scholar 

  4. Colbourn C.J.: The Combinatorics of Network Reliability. Oxford University Press, New York (1987)

    Google Scholar 

  5. Esfahanian A.H.: Generalized measures of fault tolerance with application to n-cube Networks. IEEE Trans. Comput. 38(11), 1586–1591 (1989)

    Article  Google Scholar 

  6. Esfahanian A.H., Hakimi S.L.: On computing a conditional edge-connectivity of a graph. Inf. Process. Lett. 27, 195–199 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  7. Harary F.: Conditional connectivity. Networks 13, 347–357 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  8. Li Q.L., Li Q.: Reliability analysis of circulants. Networks 31, 61–65 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  9. Liang, X.D., Meng, J.X.: Connectivity of Connected Bipartite Graphs with Two Orbits, Lecture notes in computer science, vol. 4489, pp. 334–337. Springer, Heidelberg (2007)

  10. Mader W.: Minimale n-fach kantenzusammenhängenden Graphen. Math. Ann. 191, 21–28 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  11. Meng J.X.: Optimally super-edge-connected transitive graphs. Discret. Math. 260, 239–248 (2003)

    Article  MATH  Google Scholar 

  12. Meng J.X., Ji Y.H.: On a kind of restricted edge connectivity of graphs. Discret. Appl. Math. 117, 183–193 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  13. Provan J.S., Ball M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12, 777–788 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  14. Tindell R.: Connectivity of Cayley digraphs. In: Du, D.Z., Hsu, D.F. (eds) Combinatorial Network Theory, pp. 41–46. Klumer, Dordrecht (1996)

    Google Scholar 

  15. Wang Y.Q.: Super restricted edge-connectivity of vertex-transitive graphs. Discret. Math. 289, 199–205 (2004)

    Article  MATH  Google Scholar 

  16. Wang M., Li Q.: Conditional edge connectivity properties, reliability comparison and transitivity of graphs. Discret. Math. 258, 205–214 (2002)

    Article  MATH  Google Scholar 

  17. Xu J.M., Xu K.L.: On restricted edge connectivity of graphs. Discret. Math. 243, 291–298 (2002)

    Article  MATH  Google Scholar 

  18. Xu M.Y., Huang J.H., Li H.L., Li S.R.: Introduction to Group Theory (in Chinese), pp. 379–386. Academic Publishes, New York (1999)

    Google Scholar 

  19. Zhang Z., Meng J.X.: Restricted edge connectivity of edge transitive graphs. Ars Combin. LXXVIII, 297–308 (2006)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, Xinjiang, People’s Republic of China

    Yingzhi Tian, Jixiang Meng & Xiaodong Liang

Authors
  1. Yingzhi Tian
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jixiang Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaodong Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yingzhi Tian.

Additional information

The research is supported by NSFC (No.10671165) and NSFXJ (No. 2010211A06).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tian, Y., Meng, J. & Liang, X. On Super Restricted Edge Connectivity of Half Vertex Transitive Graphs. Graphs and Combinatorics 28, 287–296 (2012). https://doi.org/10.1007/s00373-011-1035-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-011-1035-0

Keywords

Search

Navigation