Extended star graphs
Chordal graphs, which are intersection graph of subtrees of a tree, can be represented on trees. Some representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness...
Saved in:
| Date: | 2016 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Lugansk National Taras Shevchenko University
2016
|
| Subjects: | |
| Online Access: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/55 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| id |
oai:ojs.admjournal.luguniv.edu.ua:article-55 |
|---|---|
| record_format |
ojs |
| spelling |
oai:ojs.admjournal.luguniv.edu.ua:article-552016-07-12T10:09:40Z Extended star graphs Gutierrez, Marisa Tondato, Silvia Beatriz clique trees, asteroids, extended star graphs 05C75 Chordal graphs, which are intersection graph of subtrees of a tree, can be represented on trees. Some representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness of the representation. An extended star graph is the intersection graph of a family of subtrees of a tree that has exactly one vertex of degree at least three. An asteroidal triple in a graph is a set of three non-adjacent vertices such that for any two of them there exists a path between them that does not intersect the neighborhood of the third. Several subclasses of chordal graphs (interval graphs, directed path graphs) have been characterized by forbidden asteroids. In this paper, we define, a subclass of chordal graphs, called extended star graphs, prove a characterization of this class by forbidden asteroids and show open problems. Lugansk National Taras Shevchenko University 2016-07-12 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/55 Algebra and Discrete Mathematics; Vol 21, No 2 (2016) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/55/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/55/13 Copyright (c) 2016 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| baseUrl_str |
|
| datestamp_date |
2016-07-12T10:09:40Z |
| collection |
OJS |
| language |
English |
| topic |
clique trees asteroids extended star graphs 05C75 |
| spellingShingle |
clique trees asteroids extended star graphs 05C75 Gutierrez, Marisa Tondato, Silvia Beatriz Extended star graphs |
| topic_facet |
clique trees asteroids extended star graphs 05C75 |
| format |
Article |
| author |
Gutierrez, Marisa Tondato, Silvia Beatriz |
| author_facet |
Gutierrez, Marisa Tondato, Silvia Beatriz |
| author_sort |
Gutierrez, Marisa |
| title |
Extended star graphs |
| title_short |
Extended star graphs |
| title_full |
Extended star graphs |
| title_fullStr |
Extended star graphs |
| title_full_unstemmed |
Extended star graphs |
| title_sort |
extended star graphs |
| description |
Chordal graphs, which are intersection graph of subtrees of a tree, can be represented on trees. Some representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness of the representation. An extended star graph is the intersection graph of a family of subtrees of a tree that has exactly one vertex of degree at least three. An asteroidal triple in a graph is a set of three non-adjacent vertices such that for any two of them there exists a path between them that does not intersect the neighborhood of the third. Several subclasses of chordal graphs (interval graphs, directed path graphs) have been characterized by forbidden asteroids. In this paper, we define, a subclass of chordal graphs, called extended star graphs, prove a characterization of this class by forbidden asteroids and show open problems. |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2016 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/55 |
| work_keys_str_mv |
AT gutierrezmarisa extendedstargraphs AT tondatosilviabeatriz extendedstargraphs |
| first_indexed |
2025-07-17T10:36:27Z |
| last_indexed |
2025-07-17T10:36:27Z |
| _version_ |
1837890103400202240 |