<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Let <italic>G</italic> be a connected simple graph. We prove that <italic>G</italic> is a closed graph if and only if <italic>G</italic> is a proper interval graph. As a consequence we obtain that there exist linear-time algorithms for closed graph recognition.</p></abstract>

Let G be a connected simple graph. We prove that G is a closed graph if and only if G is a proper interval graph. As a consequence we obtain that there exist linear-time algorithms for closed graph recognition.

Closed graphs are proper interval graphs

Department of Mathematics and Computer Science, University of Messina, Viale Ferdinando Stagno d’Alcontres, 31 98166 Messina, Italy

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Closed graphs are proper interval graphs"}

Let G be a connected simple graph. We prove that G is a closed graph if and only if G is a proper interval graph. As a consequence we obtain that there exist...

Closed graphs are proper interval graphs

Online veröffentlicht: 22. Dez. 2015

Seitenbereich: 37 - 44

Eingereicht: 18. Sept. 2013

Akzeptiert: 13. Nov. 2013

DOI: https://doi.org/10.2478/auom-2014-0048

Schlüsselwörter
Closed graphs, interval graphs, Gröbner bases

© 2014 Marilena Crupi et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Closed graphs are proper interval graphs

Online veröffentlicht: 22. Dez. 2015

Seitenbereich: 37 - 44

Eingereicht: 18. Sept. 2013

Akzeptiert: 13. Nov. 2013

DOI: https://doi.org/10.2478/auom-2014-0048

SchlüsselwörterClosed graphs, interval graphs, Gröbner bases

© 2014 Marilena Crupi et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Schlüsselwörter
Closed graphs, interval graphs, Gröbner bases