Closed graphs are proper interval graphs

Marilena Crupi; Giancarlo Rinaldo

doi:10.2478/auom-2014-0048

.blurhash-client-img { display: none !important; }

Closed graphs are proper interval graphs

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

Volume 22 (2014): Issue 3 (September 2014)

By: Marilena Crupi and Giancarlo Rinaldo

Open Access

|Dec 2015

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.

References

[1] K.S. Booth, G.S. Lucker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13 (1976), 335–379.10.1016/S0022-0000(76)80045-1
Search in Google Scholar
[2] D. G. Corneil, A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, Discrete Appl. Math., 138 (2004), 371–379.10.1016/j.dam.2003.07.001
Search in Google Scholar
[3] D. A. Cox, A. Erskine, On closed graphs, (2013) arXiv:1306.5149v1.
Search in Google Scholar
[4] M. Crupi, G. Rinaldo, Binomial edge ideals with quadratic Gröbner bases, Electron. J. Combin, 18 (2011) P#211, 1–13.10.37236/698
Search in Google Scholar
[5] M. Drton, B. Sturmfels, S. Sullivan, Lectures on Algebraic statistics, Birhäuser, Boston, Cambridge, 2009.10.1007/978-3-7643-8905-5
Search in Google Scholar
[6] D. Eisenbud, B. Sturmfels, Binomial ideals, Duke Math. J., 84 (1996), 1–45.10.1215/S0012-7094-96-08401-X
Search in Google Scholar
[7] C. M. H. Figueiredo, J. Meidanis, C. P. Mello, A linear-time algorithm for proper interval graph recognition, Inform. Process. Lett., 56 (3) (1995), 179–184.10.1016/0020-0190(95)00133-W
Search in Google Scholar
[8] F. Gardi, The Roberts characterization of proper and unit interval graphs, Discrete Math., 307(22) (2007), 2906–2908.10.1016/j.disc.2006.04.043
Search in Google Scholar
[9] P. W. Golberg, M. C. Golumbic, H. Kaplan, R. Shamir, Four strikes against physical mapping of DNA, J. Comput. Biol., 2 (1995), 139–152.10.1089/cmb.1995.2.139
Search in Google Scholar
[10] M. C. Golumbic, Algorithm Graph Theory and Perfect graphs, Academic Press, New York, N.Y., 1980.10.1016/B978-0-12-289260-8.50010-8
Search in Google Scholar
[11] M. Habib, R. McConnel, C. Paul, L.Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive one testing, Theoret. Comput. Sci., 234 (2000), 59–8410.1016/S0304-3975(97)00241-7
Search in Google Scholar
[12] G. Hajós, Über eine Art von Graphen, Internat. Math. Nachrichten, 11(1957) problem 65.
Search in Google Scholar
[13] P. Heggernes, D. Meister, C. Papadopoulos, A new representation of proper interval graphs with an application to clique-width, DIMAP Workshop on Algorithmic Graph Theory 2009, Electron. Notes Discrete Math., 32 (2009), 27–34.10.1016/j.endm.2009.02.005
Search in Google Scholar
[14] J. Herzog, T. Hibi, F. Hreinsdottir, T. Kahle, J. Rauh, Binomial edge ideals and conditional independence statements, Adv. in Appl. Math., 45 (2010), 317–33310.1016/j.aam.2010.01.003
Search in Google Scholar
[15] J. Herzog, T. Hibi, Monomial ideals, Grad. Texts in Math., Springer, 2010.10.1007/978-0-85729-106-6
Search in Google Scholar
[16] J. Herzog, V. Ene, T. Hibi, Cohen-Macaulay binomial edge ideals, Nagoya Math. J., 204 (2011), 57–68.10.1215/00277630-1431831
Search in Google Scholar
[17] P. Hell and J. Huang, Certifying LexBFS Regognition Algorithms for Proper Interval graphs and proper Interval Bigraphs, SIAM J. Discrete Math., 18 (2005), 554–570.10.1137/S0895480103430259
Search in Google Scholar
[18] P. J. Looges, S. Olariu, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl., 25 (1993), 15–25.10.1016/0898-1221(93)90308-I
Search in Google Scholar
[19] K. Matsuda, Weakly closed graphs and F-purity of binomial edge ideals, (2012) arXiv:1209.4300v1.
Search in Google Scholar
[20] D. Meister, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Discrete Appl. Math., 146 (2005), 193–218.10.1016/j.dam.2004.10.001
Search in Google Scholar
[21] M. Ohtani, Graphs and ideals generated by some 2-minors, Comm. Algebra, 39 (3) (2011), 905–917.10.1080/00927870903527584
Search in Google Scholar
[22] B. S. Panda, S. K. Das A linear time recognition algorithm for proper interval graphs, Inform. Process. Lett., 87 (2003), 153–161.10.1016/S0020-0190(03)00298-9
Search in Google Scholar
[23] F.S. Roberts, Indifference graphs, In Proof Techniques in Graph Theory (F. Harary, ed.), (1969), 139–146. Academic Press, New York, NY.
Search in Google Scholar
[24] D. Rose, G. Lueker, R. E. Tarjan, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5 (1976), 266–283.10.1137/0205021
Search in Google Scholar
[25] M.S. Waterman, J.R. Griccs, Interval graphs and maps of DNA, Bull. Math. Biol., 48 (1986), 189–195.10.1016/S0092-8240(86)80006-4
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.2478/auom-2014-0048 | Journal eISSN: 1844-0835 | Journal ISSN: 1224-1784

Journal RSS Feed

Language: English

Page range: 37 - 44

Submitted on: Sep 18, 2013

Accepted on: Nov 13, 2013

Published on: Dec 22, 2015

Published by: Ovidius University of Constanta

In partnership with: Paradigm Publishing Services

Publication frequency: 3 issues per year

Keywords:

Related subjects:

© 2015 Marilena Crupi, Giancarlo Rinaldo, published by Ovidius University of Constanta
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 22 (2014): Issue 3 (September 2014)