The Number of Blocks of a Graph with Given Minimum Degree
A block of a graph is a nonseparable maximal subgraph of the graph. We denote by bG the number of block of a graph G. We show that, for a connected graph G of order n with minimum degree k≥1, bG<2k−3/k2−k−1n. The bound is asymptotically tight. In addition, for a connected cubic graph G of order n...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2021/6691960 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832559805049339904 |
|---|---|
| author | Lei Li Baoyindureng Wu |
| author_facet | Lei Li Baoyindureng Wu |
| author_sort | Lei Li |
| collection | DOAJ |
| description | A block of a graph is a nonseparable maximal subgraph of the graph. We denote by bG the number of block of a graph G. We show that, for a connected graph G of order n with minimum degree k≥1, bG<2k−3/k2−k−1n. The bound is asymptotically tight. In addition, for a connected cubic graph G of order n≥14, bG≤n/2−2. The bound is tight. |
| format | Article |
| id | doaj-art-f700950a21d54fcd98c8a405409cb191 |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-f700950a21d54fcd98c8a405409cb1912025-02-03T01:29:21ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2021-01-01202110.1155/2021/66919606691960The Number of Blocks of a Graph with Given Minimum DegreeLei Li0Baoyindureng Wu1College of Mathematics and System Sciences, Xinjiang University Urumqi, Xinjiang 830046, ChinaCollege of Mathematics and System Sciences, Xinjiang University Urumqi, Xinjiang 830046, ChinaA block of a graph is a nonseparable maximal subgraph of the graph. We denote by bG the number of block of a graph G. We show that, for a connected graph G of order n with minimum degree k≥1, bG<2k−3/k2−k−1n. The bound is asymptotically tight. In addition, for a connected cubic graph G of order n≥14, bG≤n/2−2. The bound is tight.http://dx.doi.org/10.1155/2021/6691960 |
| spellingShingle | Lei Li Baoyindureng Wu The Number of Blocks of a Graph with Given Minimum Degree Discrete Dynamics in Nature and Society |
| title | The Number of Blocks of a Graph with Given Minimum Degree |
| title_full | The Number of Blocks of a Graph with Given Minimum Degree |
| title_fullStr | The Number of Blocks of a Graph with Given Minimum Degree |
| title_full_unstemmed | The Number of Blocks of a Graph with Given Minimum Degree |
| title_short | The Number of Blocks of a Graph with Given Minimum Degree |
| title_sort | number of blocks of a graph with given minimum degree |
| url | http://dx.doi.org/10.1155/2021/6691960 |
| work_keys_str_mv | AT leili thenumberofblocksofagraphwithgivenminimumdegree AT baoyindurengwu thenumberofblocksofagraphwithgivenminimumdegree AT leili numberofblocksofagraphwithgivenminimumdegree AT baoyindurengwu numberofblocksofagraphwithgivenminimumdegree |