A Characterization of 2-Tree Probe Interval Graphs

David E. Brown; Breeann M. Flesch; J. Richard

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 3, page 509-527
  • ISSN: 2083-5892

Abstract

top
A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231]

How to cite

top

David E. Brown, Breeann M. Flesch, and J. Richard. "A Characterization of 2-Tree Probe Interval Graphs." Discussiones Mathematicae Graph Theory 34.3 (2014): 509-527. <http://eudml.org/doc/268020>.

@article{DavidE2014,
abstract = {A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231]},
author = {David E. Brown, Breeann M. Flesch, J. Richard},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {interval graph; probe interval graph; 2-tree},
language = {eng},
number = {3},
pages = {509-527},
title = {A Characterization of 2-Tree Probe Interval Graphs},
url = {http://eudml.org/doc/268020},
volume = {34},
year = {2014},
}

TY - JOUR
AU - David E. Brown
AU - Breeann M. Flesch
AU - J. Richard
TI - A Characterization of 2-Tree Probe Interval Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 3
SP - 509
EP - 527
AB - A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231]
LA - eng
KW - interval graph; probe interval graph; 2-tree
UR - http://eudml.org/doc/268020
ER -

References

top
  1. [1] L.W. Beineke, Characterizations of derived graphs, J. Combin. Theory 9 (1970) 129-135. doi:10.1016/S0021-9800(70)80019-9[Crossref] Zbl0202.55702
  2. [2] L.W. Beineke and R.E. Pippert, Properties and characterizations of k-trees, Math- ematika 18 (1971) 141-151. doi:10.1112/S0025579300008500[Crossref] Zbl0221.05057
  3. [3] D.E. Brown, Variations on Interval Graphs, PhD Thesis, (Univ. of Colorado, Den- ver, USA, 2004). 
  4. [4] D.E. Brown, A.H. Busch and G. Isaak, Linear time recognition algorithms and struc- ture theorems for bipartite tolerance graphs and bipartite probe interval graphs, Dis- crete Math. Theor. Comput. Sci. 12(5) (2010) 63-82. Zbl1280.68142
  5. [5] D.E. Brown, S.C. Flink and J.R. Lundgren, Interval k-graphs, in: Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002) 156 (2002) 5-16. Zbl1022.05073
  6. [6] D.E. Brown and L.J. Langley, Forbidden subgraph characterizations of bipartite unit probe interval graphs, Australas. J. Combin. 52 (2012) 19-31. Zbl1251.05133
  7. [7] D.E. Brown and J.R. Lundgren, Bipartite probe interval graphs, circular arc graphs, and interval point bigraphs, Australas. J. Combin. 35 (2006) 221-236. Zbl1095.05030
  8. [8] D.E. Brown, J.R. Lundgren and L. Sheng, A characterization of cycle-free unit probe interval graphs, Discrete Appl. Math. 157 (2009) 762-767. doi:10.1016/j.dam.2008.07.004[WoS][Crossref] Zbl1172.05345
  9. [9] P.C. Fishburn, Interval Orders and Interval Graphs (Wiley & Sons, 1985). 
  10. [10] B. Flesch and J.R. Lundgren, A characterization of k-trees that are interval p-graphs, Australas. J. Combin. 49 (2011) 227-237. Zbl1228.05219
  11. [11] D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835-855. doi:10.2140/pjm.1965.15.835[Crossref] Zbl0132.21001
  12. [12] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
  13. [13] M.C. Golumbic and M. Lipshteyn, On the hierarchy of interval, probe and tolerance graphs, in: Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001) 153 (2001) 97-106. Zbl0995.05104
  14. [14] M.C. Golumbic and A.N. Trenk, Tolerance Graphs, Cambridge Studies in Advanced Mathematics, Vol. 18 (Cambridge University Press, Cambridge, 2004). Zbl1091.05001
  15. [15] C.G. Lekkerkerker and J.Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962/1963) 45-64. Zbl0105.17501
  16. [16] R. McConnell and Y. Nussbaum, Linear-time recognition of probe interval graphs, in: Proceedings of the 17th Annual European Symposium, Algorithms-ESA 2009, Lecture Notes in Comput. Sci. 5757 (2009) 349-360. doi:10.1007/978-3-642-04128-0 32[Crossref] Zbl1256.05236
  17. [17] F.R. McMorris, C. Wang and P. Zhang, On probe interval graphs, Discrete Appl. Math. 88 (1998) 315-324. doi:10.1016/S0166-218X(98)00077-8[Crossref] Zbl0918.05087
  18. [18] A. Proskurowski, Separating subgraphs in k-trees: cables and caterpillars, Discrete Math. 49 (1984) 275-285. doi:10.1016/0012-365X(84)90164-X[Crossref] 
  19. [19] N. Pržulj and D.G. Corneil, 2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231. doi:10.1016/j.dam.2004.06.015[Crossref] 
  20. [20] F.S. Roberts, Discrete Mathematical Models (Prentice-Hall, Upper Saddle River, NJ, 1976). 
  21. [21] L. Sheng, Cycle free probe interval graphs, in: Proceedings of the Thirtieth South- eastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999) 140 (1999) 33-42. Zbl0960.05085
  22. [22] P. Zhang, Methods of mapping DNA fragments, United States Patent, 1997 http://www.cc.columbia.edu/cu/cie/techlists/patents/5667970.htm 
  23. [23] P. Zhang, E.A. Schon, E. Cayanis, J.Weiss, S. Kistler and P.E. Bourne, An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA, Comput. Appl. Biosci. 10(3) (1994) 309-317. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.