Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs
The 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph. Such 2-trees can be characterized both as the edge-minimal chordal graphs and also as...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Georgia Southern University
2021-03-01
|
| Series: | Theory and Applications of Graphs |
| Subjects: | |
| Online Access: | https://digitalcommons.georgiasouthern.edu/tag/vol8/iss1/4 |
| _version_ | 1818441717867610112 |
|---|---|
| author | Terry McKee |
| author_facet | Terry McKee |
| author_sort | Terry McKee |
| collection | DOAJ |
| description | The 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph. Such 2-trees can be characterized both as the edge-minimal chordal graphs and also as the edge-maximal series-parallel graphs. These are also precisely the 2-connected graphs that are simultaneously chordal and series-parallel, where these latter two better-known types of graphs have themselves been both characterized and applied in numerous ways that are unmotivated by their interaction with 2-trees and with each other.
Toward providing such motivation, the present paper examines several simple, very closely-related characterizations of chordal graphs and 2-trees and, after that, of series-parallel graphs and 2-trees. This leads to showing a way in which chordal graphs and series-parallel graphs are special---indeed, extremal---in this regard. |
| first_indexed | 2024-12-14T18:32:42Z |
| format | Article |
| id | doaj.art-fe11d9f6ed394dfdb13e072a2a743145 |
| institution | Directory Open Access Journal |
| issn | 2470-9859 |
| language | English |
| last_indexed | 2024-12-14T18:32:42Z |
| publishDate | 2021-03-01 |
| publisher | Georgia Southern University |
| record_format | Article |
| series | Theory and Applications of Graphs |
| spelling | doaj.art-fe11d9f6ed394dfdb13e072a2a7431452022-12-21T22:51:44ZengGeorgia Southern UniversityTheory and Applications of Graphs2470-98592021-03-018110.20429/tag.2021.080104Characterizing 2-Trees Relative to Chordal and Series-Parallel GraphsTerry McKeeThe 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph. Such 2-trees can be characterized both as the edge-minimal chordal graphs and also as the edge-maximal series-parallel graphs. These are also precisely the 2-connected graphs that are simultaneously chordal and series-parallel, where these latter two better-known types of graphs have themselves been both characterized and applied in numerous ways that are unmotivated by their interaction with 2-trees and with each other. Toward providing such motivation, the present paper examines several simple, very closely-related characterizations of chordal graphs and 2-trees and, after that, of series-parallel graphs and 2-trees. This leads to showing a way in which chordal graphs and series-parallel graphs are special---indeed, extremal---in this regard.https://digitalcommons.georgiasouthern.edu/tag/vol8/iss1/42-treechordal graphseries-parallel graph |
| spellingShingle | Terry McKee Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs Theory and Applications of Graphs 2-tree chordal graph series-parallel graph |
| title | Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs |
| title_full | Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs |
| title_fullStr | Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs |
| title_full_unstemmed | Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs |
| title_short | Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs |
| title_sort | characterizing 2 trees relative to chordal and series parallel graphs |
| topic | 2-tree chordal graph series-parallel graph |
| url | https://digitalcommons.georgiasouthern.edu/tag/vol8/iss1/4 |
| work_keys_str_mv | AT terrymckee characterizing2treesrelativetochordalandseriesparallelgraphs |