<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

Pubblicato online: 22 dic 2015

Pagine: 37 - 44

Ricevuto: 18 set 2013

Accettato: 13 nov 2013

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

Parole chiave
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

Pubblicato online: 22 dic 2015

Pagine: 37 - 44

Ricevuto: 18 set 2013

Accettato: 13 nov 2013

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

Parole chiaveClosed 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.

Parole chiave
Closed graphs, interval graphs, Gröbner bases