Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Probe (unit) interval graphs form a superclass of (unit) interval graphs. A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe interval graphs were introduced by Zhang for an application concerning with the physical mapping of DNA in the human genome project. In this work, we present characterizations by minimal forbidden induced subgraphs of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. © 2011 Elsevier B.V.

Registro:

Documento: Artículo
Título:Probe interval and probe unit interval graphs on superclasses of cographs
Autor:Durán, G.; Grippo, L.N.; Safe, M.D.
Filiación:CONICET, Argentina
Depto. de Matemática, FCEN, Universidad de Buenos Aires, Argentina
Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Chile
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina
Depto. de Computación, FCEN, Universidad de Buenos Aires, Argentina
Palabras clave:Forbidden induced subgraphs; P4-tidy graphs; Probe interval graphs; Probe unit interval graphs; Tree-cographs
Año:2011
Volumen:37
Número:C
Página de inicio:339
Página de fin:344
DOI: http://dx.doi.org/10.1016/j.endm.2011.05.058
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p339_Duran

Referencias:

  • Brown, D.E., Ludgren, J.R., Bipartite probe interval graphs, interval point bigraphs, and circular-arc graphs (2006) Australas. J. Combin., 35, pp. 221-236
  • Brown, D.E., Ludgren, J.R., Sheng, L., A characterization of cycle-free unit probe interval graphs (2009) Discrete Appl. Math., 157, pp. 762-767
  • Chandler, D., Chang, M., Kloks, T., Liu, J., Peng, S., On probe permutation graphs (2009) Discrete Appl. Math., 157, pp. 2611-2619
  • Giakoumakis, V., Roussel, F., Thuillier, H., On P4-tidy graphs (1997) Discrete Math. Theor. Comput. Sci., 1, pp. 17-41
  • Golumbic, M.C., Lipshteyn, M., Chordal probe graphs (2004) Discrete Appl. Math., 143, pp. 221-237
  • Hoàng, C.T., (1985), "Perfect graphs," Ph.D. thesis, McGill University, Canada; Jamison, B., Olariu, S., A new class of brittle graphs (1989) Studies in Applied Mathematics, 81, pp. 89-92
  • Jamison, B., Olariu, S., On a unique tree representation for P4-extendible graphs (1991) Discrete Appl. Math., 34, pp. 151-164
  • Le, V., de Ridder, H., Probe split graphs (2007) Discrete Math. Theor. Comput. Sci., 9, pp. 207-238
  • Lekkerkerker, C., Boland, D., Representation of finite graphs by a set of intervals on the real line (1962) Fundam. Math., 51, pp. 45-64
  • Pržulj, N., Corneil, D., 2-tree probe interval graphs have a large obstruction set (2005) Discrete Appl. Math., 150, pp. 216-231
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , Academic Press, F. Harary (Ed.)
  • Sheng, L., Cycle-free probe interval graphs (1999) Congr. Numer., 140, pp. 33-42
  • Tinhofer, G., Strong tree-cographs are Birkoff graphs (1988) Discrete Appl. Math., 22, pp. 275-288
  • Zhang, P., Probe interval graphs and its applications to physical mapping of DNA, Manuscript (1994)

Citas:

---------- APA ----------
Durán, G., Grippo, L.N. & Safe, M.D. (2011) . Probe interval and probe unit interval graphs on superclasses of cographs. Electronic Notes in Discrete Mathematics, 37(C), 339-344.
http://dx.doi.org/10.1016/j.endm.2011.05.058
---------- CHICAGO ----------
Durán, G., Grippo, L.N., Safe, M.D. "Probe interval and probe unit interval graphs on superclasses of cographs" . Electronic Notes in Discrete Mathematics 37, no. C (2011) : 339-344.
http://dx.doi.org/10.1016/j.endm.2011.05.058
---------- MLA ----------
Durán, G., Grippo, L.N., Safe, M.D. "Probe interval and probe unit interval graphs on superclasses of cographs" . Electronic Notes in Discrete Mathematics, vol. 37, no. C, 2011, pp. 339-344.
http://dx.doi.org/10.1016/j.endm.2011.05.058
---------- VANCOUVER ----------
Durán, G., Grippo, L.N., Safe, M.D. Probe interval and probe unit interval graphs on superclasses of cographs. Electron. Notes Discrete Math. 2011;37(C):339-344.
http://dx.doi.org/10.1016/j.endm.2011.05.058