On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs
A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. W...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2014-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1724 |
| _version_ | 1797718015381340160 |
|---|---|
| author | Wang Dingguo Shan Erfang |
| author_facet | Wang Dingguo Shan Erfang |
| author_sort | Wang Dingguo |
| collection | DOAJ |
| description | A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds. |
| first_indexed | 2024-03-12T08:44:49Z |
| format | Article |
| id | doaj.art-5c68b11595ae4755a71200b947d21fe1 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:49Z |
| publishDate | 2014-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-5c68b11595ae4755a71200b947d21fe12023-09-02T16:30:01ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922014-02-0134112713610.7151/dmgt.1724dmgt.1724On the Numbers of Cut-Vertices and End-Blocks in 4-Regular GraphsWang Dingguo0Shan Erfang1Department of Mathematics, Shanghai University, Shanghai 200444, ChinaSchool of Management, Shanghai University, Shanghai 200444, China 2Department of Mathematics, Shanghai University, Shanghai 200444, ChinaA cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.https://doi.org/10.7151/dmgt.17244-regular graphclaw-freecut-verticesend-blocks |
| spellingShingle | Wang Dingguo Shan Erfang On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs Discussiones Mathematicae Graph Theory 4-regular graph claw-free cut-vertices end-blocks |
| title | On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs |
| title_full | On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs |
| title_fullStr | On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs |
| title_full_unstemmed | On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs |
| title_short | On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs |
| title_sort | on the numbers of cut vertices and end blocks in 4 regular graphs |
| topic | 4-regular graph claw-free cut-vertices end-blocks |
| url | https://doi.org/10.7151/dmgt.1724 |
| work_keys_str_mv | AT wangdingguo onthenumbersofcutverticesandendblocksin4regulargraphs AT shanerfang onthenumbersofcutverticesandendblocksin4regulargraphs |