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:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2016
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/155241 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Extended star graphs / M. Gutierrez, S.B. Tondato // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 239–254. — Бібліогр.: 16 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-155241 |
|---|---|
| record_format |
dspace |
| spelling |
Gutierrez, M. Tondato, S.B. 2019-06-16T14:33:45Z 2019-06-16T14:33:45Z 2016 Extended star graphs / M. Gutierrez, S.B. Tondato // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 239–254. — Бібліогр.: 16 назв. — англ. 1726-3255 2010 MSC:05C75. https://nasplib.isofts.kiev.ua/handle/123456789/155241 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. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Extended star graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Extended star graphs |
| spellingShingle |
Extended star graphs Gutierrez, M. Tondato, S.B. |
| 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 |
| author |
Gutierrez, M. Tondato, S.B. |
| author_facet |
Gutierrez, M. Tondato, S.B. |
| publishDate |
2016 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| 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.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/155241 |
| citation_txt |
Extended star graphs / M. Gutierrez, S.B. Tondato // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 239–254. — Бібліогр.: 16 назв. — англ. |
| work_keys_str_mv |
AT gutierrezm extendedstargraphs AT tondatosb extendedstargraphs |
| first_indexed |
2025-12-07T18:19:51Z |
| last_indexed |
2025-12-07T18:19:51Z |
| _version_ |
1850874623624740864 |