<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

Data publikacji: 22 gru 2015

Zakres stron: 37 - 44

Otrzymano: 18 wrz 2013

Przyjęty: 13 lis 2013

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

Słowa kluczowe
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

Data publikacji: 22 gru 2015

Zakres stron: 37 - 44

Otrzymano: 18 wrz 2013

Przyjęty: 13 lis 2013

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

Słowa kluczoweClosed 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.

Słowa kluczowe
Closed graphs, interval graphs, Gröbner bases