Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges
Let G be a 4-connected graph, and let E ̃ (G) denote the set of those edges of G which are not contained in a triangle, and let E c (G) denote the set of 4-contractible edges of G . We show that if 3 ≤ | E ̃ (G) | ≤ 4 or | E ̃ (G) | ≥ 7 , then | E c (G) | ≥ (| E ̃ (G) | + 8) ∕ 4 unless G has one of...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2018-08-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S0972860017301159 |
| _version_ | 1819074342145753088 |
|---|---|
| author | Yoshimi Egawa Keiko Kotani Shunsuke Nakamura |
| author_facet | Yoshimi Egawa Keiko Kotani Shunsuke Nakamura |
| author_sort | Yoshimi Egawa |
| collection | DOAJ |
| description | Let G be a 4-connected graph, and let E ̃ (G) denote the set of those edges of G which are not contained in a triangle, and let E c (G) denote the set of 4-contractible edges of G . We show that if 3 ≤ | E ̃ (G) | ≤ 4 or | E ̃ (G) | ≥ 7 , then | E c (G) | ≥ (| E ̃ (G) | + 8) ∕ 4 unless G has one of the three specified configurations. Keywords: 4-connected graph, Contractible edge, Triangle |
| first_indexed | 2024-12-21T18:07:59Z |
| format | Article |
| id | doaj.art-bbe8933221364ac4a5f822a35b6ad419 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 |
| language | English |
| last_indexed | 2024-12-21T18:07:59Z |
| publishDate | 2018-08-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-bbe8933221364ac4a5f822a35b6ad4192022-12-21T18:54:53ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002018-08-01152202210Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edgesYoshimi Egawa0Keiko Kotani1Shunsuke Nakamura2Department of Applied Mathematics, Tokyo University of Science, Shinjuku-ku, Tokyo, 162-8601, JapanDepartment of Mathematics, Tokyo University of Science, Shinjuku-ku, Tokyo, 162-8601, JapanDepartment of Applied Mathematics, Tokyo University of Science, Shinjuku-ku, Tokyo, 162-8601, Japan; Corresponding author.Let G be a 4-connected graph, and let E ̃ (G) denote the set of those edges of G which are not contained in a triangle, and let E c (G) denote the set of 4-contractible edges of G . We show that if 3 ≤ | E ̃ (G) | ≤ 4 or | E ̃ (G) | ≥ 7 , then | E c (G) | ≥ (| E ̃ (G) | + 8) ∕ 4 unless G has one of the three specified configurations. Keywords: 4-connected graph, Contractible edge, Trianglehttp://www.sciencedirect.com/science/article/pii/S0972860017301159 |
| spellingShingle | Yoshimi Egawa Keiko Kotani Shunsuke Nakamura Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges AKCE International Journal of Graphs and Combinatorics |
| title | Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges |
| title_full | Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges |
| title_fullStr | Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges |
| title_full_unstemmed | Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges |
| title_short | Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges |
| title_sort | structure of edges in a 4 connected graph not contained in triangles and the number of contractible edges |
| url | http://www.sciencedirect.com/science/article/pii/S0972860017301159 |
| work_keys_str_mv | AT yoshimiegawa structureofedgesina4connectedgraphnotcontainedintrianglesandthenumberofcontractibleedges AT keikokotani structureofedgesina4connectedgraphnotcontainedintrianglesandthenumberofcontractibleedges AT shunsukenakamura structureofedgesina4connectedgraphnotcontainedintrianglesandthenumberofcontractibleedges |