<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

Published Online: Dec 22, 2015

Page range: 37 - 44

Received: Sep 18, 2013

Accepted: Nov 13, 2013

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

Keywords
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

Published Online: Dec 22, 2015

Page range: 37 - 44

Received: Sep 18, 2013

Accepted: Nov 13, 2013

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

KeywordsClosed 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.

Keywords
Closed graphs, interval graphs, Gröbner bases