Structures of Critical Nontree Graphs with Cutwidth Four
The cutwidth of a graph <i>G</i> is the smallest integer <i>k</i> (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>1</mn>...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/7/1631 |
| _version_ | 1797607480490983424 |
|---|---|
| author | Zhenkun Zhang Hongjian Lai |
| author_facet | Zhenkun Zhang Hongjian Lai |
| author_sort | Zhenkun Zhang |
| collection | DOAJ |
| description | The cutwidth of a graph <i>G</i> is the smallest integer <i>k</i> (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>) such that the vertices of <i>G</i> are arranged in a linear layout <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>[</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>]</mo></mrow></semantics></math></inline-formula>, in such a way that for each <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula>, there are at most <i>k</i> edges with one endpoint in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo>}</mo></mrow></semantics></math></inline-formula> and the other in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><msub><mi>v</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>}</mo></mrow></semantics></math></inline-formula>. The cutwidth problem for <i>G</i> is to determine the cutwidth <i>k</i> of <i>G</i>. A graph <i>G</i> with cutwidth <i>k</i> is <i>k</i>-cutwidth critical if every proper subgraph of <i>G</i> has a cutwidth less than <i>k</i> and <i>G</i> is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>v</mi><mn>0</mn></msub></semantics></math></inline-formula>, and graph class with a central cycle <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><mi>q</mi></msub></semantics></math></inline-formula> of length <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>q</mi><mo>≤</mo><mn>6</mn></mrow></semantics></math></inline-formula>, respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">S</mi></semantics></math></inline-formula> with cardinality 2, 3 or 4, where each member of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">S</mi></semantics></math></inline-formula> is either a 2-cutwith graph or a 3-cutwidth graph. |
| first_indexed | 2024-03-11T05:30:32Z |
| format | Article |
| id | doaj.art-44d9d584b83f4e2483e780e8a55f78f4 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T05:30:32Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-44d9d584b83f4e2483e780e8a55f78f42023-11-17T17:08:24ZengMDPI AGMathematics2227-73902023-03-01117163110.3390/math11071631Structures of Critical Nontree Graphs with Cutwidth FourZhenkun Zhang0Hongjian Lai1School of Mathematics and Statistics, Huanghuai University, Zhumadian 463000, ChinaDepartment of Mathematics, West Virginia University, Morgantown, WV 26506, USAThe cutwidth of a graph <i>G</i> is the smallest integer <i>k</i> (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>) such that the vertices of <i>G</i> are arranged in a linear layout <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>[</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>]</mo></mrow></semantics></math></inline-formula>, in such a way that for each <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula>, there are at most <i>k</i> edges with one endpoint in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo>}</mo></mrow></semantics></math></inline-formula> and the other in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><msub><mi>v</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>}</mo></mrow></semantics></math></inline-formula>. The cutwidth problem for <i>G</i> is to determine the cutwidth <i>k</i> of <i>G</i>. A graph <i>G</i> with cutwidth <i>k</i> is <i>k</i>-cutwidth critical if every proper subgraph of <i>G</i> has a cutwidth less than <i>k</i> and <i>G</i> is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>v</mi><mn>0</mn></msub></semantics></math></inline-formula>, and graph class with a central cycle <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><mi>q</mi></msub></semantics></math></inline-formula> of length <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>q</mi><mo>≤</mo><mn>6</mn></mrow></semantics></math></inline-formula>, respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">S</mi></semantics></math></inline-formula> with cardinality 2, 3 or 4, where each member of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">S</mi></semantics></math></inline-formula> is either a 2-cutwith graph or a 3-cutwidth graph.https://www.mdpi.com/2227-7390/11/7/1631graph labelingcutwidthcritical graphgraph decomposition |
| spellingShingle | Zhenkun Zhang Hongjian Lai Structures of Critical Nontree Graphs with Cutwidth Four Mathematics graph labeling cutwidth critical graph graph decomposition |
| title | Structures of Critical Nontree Graphs with Cutwidth Four |
| title_full | Structures of Critical Nontree Graphs with Cutwidth Four |
| title_fullStr | Structures of Critical Nontree Graphs with Cutwidth Four |
| title_full_unstemmed | Structures of Critical Nontree Graphs with Cutwidth Four |
| title_short | Structures of Critical Nontree Graphs with Cutwidth Four |
| title_sort | structures of critical nontree graphs with cutwidth four |
| topic | graph labeling cutwidth critical graph graph decomposition |
| url | https://www.mdpi.com/2227-7390/11/7/1631 |
| work_keys_str_mv | AT zhenkunzhang structuresofcriticalnontreegraphswithcutwidthfour AT hongjianlai structuresofcriticalnontreegraphswithcutwidthfour |