Contractible Edges and Peripheral Cycles in 3-Connected Graphs

Authors

  • Alexander Slodkowski University of Texas Rio Grande Valley
  • Dr. Timothy Huber Mentor, University of Texas Rio Gran Valley

DOI:

https://doi.org/10.47611/jsr.v10i2.1193

Keywords:

contractible edges, induced subgraphs, non-separating cycles, peripheral cycles, 3-connected graphs

Abstract

Peripheral cycles (induced non-separating cycles) in a general 3-connected graph are analogous to the faces of a polyhedron. Using the works of various authors, this paper explores the distribution of contractible edges in 3-connected graphs as needed to prove a major result originally by Tutte: each edge in a 3-connected graph is part of at least 2 peripheral cycles that share only the edge and its end vertices. A complete, alternative proof of this theorem is provided. The inductive step is generalized into a new independent lemma, which states that each edge in a 3-connected graph with a non-adjacent contractible edge has at least as many peripheral cycles as in the contracted one.

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

References or Bibliography

K. Ando, H. Enomoto, and A. Saito, Contractible edges in 3-connected graphs. J. Combin. Theory Ser. B 42 (1987), 87-93.

https://doi.org/10.1016/0095-8956(87)90065-7

R. Diestel, Graph Theory. Springer, NY (2005).

R. Halin, Zur Theorie der n-fach zusammenhängenden Graphen, Abh. Math. Sem. Univ. Hamburg 33 (1969), 133-164.

https://doi.org/10.1007/BF02992931

A. Kelmans, A new planarity criterion for 3-connected graphs, J. Graph Theory 5 (1981), 259-267.

https://doi.org/10.1002/jgt.3190050307

K. Ota and A. Saito, Non-separating induced cycles in 3-connected graphs. Scientia Ser. A 2 (1988) 101-105.

A. Saito, Covering contractible edges in 3-connected graphs; I: covers of size three are cutsets. J. Graph Theory 14 (1990), 635-643.

https://doi.org/10.1002/jgt.3190140603

R. Thomas, Lecture 7. Web. https://people.math.gatech.edu/~thomas/TEACH/6014/lecture7.pdf

C. Thomassen, Planarity and duality of finite and infinite graphs, J. Combin. Theory Ser. B 29 (1980), 244-271.

https://doi.org/10.1016/0095-8956(80)90083-0

W. T. Tutte, A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64 (1961) 441-455.

https://doi.org/10.1016/S1385-7258(61)50045-5

W. T. Tutte, How to draw a graph. Proc. London Math. Soc. (3) 13 (1963) 743-68.

https://doi.org/10.1112/plms/s3-13.1.743

Published

07-03-2021

How to Cite

Slodkowski, A., & Huber, T. . (2021). Contractible Edges and Peripheral Cycles in 3-Connected Graphs. Journal of Student Research, 10(2). https://doi.org/10.47611/jsr.v10i2.1193

Issue

Vol. 10 No. 2 (2021)

Section

Research Articles

Copyright (c) 2021 Alexander Slodkowski; Dr. Timothy Huber

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Copyright holder(s) granted JSR a perpetual, non-exclusive license to distriute & display this article.