Artículo
Bonomo, F.; Durán, G.; Grippo, L.N.; Safe, M.D. "Probe interval graphs and probe unit interval graphs on superclasses of cographs" (2013) Discrete Mathematics and Theoretical Computer Science. 15(2):177-194
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
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 (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe G) graphs with disconnected complement for every graph class G with a companion. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
Registro:
| Documento: | Artículo |
| Título: | Probe interval graphs and probe unit interval graphs on superclasses of cographs |
| Autor: | Bonomo, F.; Durán, G.; Grippo, L.N.; Safe, M.D. |
| Filiación: | CONICET, Argentina Depto. de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina Depto. de Matemática and Instituto de Cálculo, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina |
| Palabras clave: | Forbidden induced subgraphs; P4-tidy graphs; Probe interval graphs; Probe unit interval graphs; Treecographs; Forbidden induced subgraphs; Human Genome Project; Interval graph; Physical mapping; Probe interval graphs; Probe intervals; Treecographs; Unit interval graphs; Forestry; Graphic methods; Probes; Trees (mathematics); Forestry; Mathematics; Trees |
| Año: | 2013 |
| Volumen: | 15 |
| Número: | 2 |
| Página de inicio: | 177 |
| Página de fin: | 194 |
| Título revista: | Discrete Mathematics and Theoretical Computer Science |
| Título revista abreviado: | Discrete Math. Theor. Comput. Sci. |
| ISSN: | 14627264 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p177_Bonomo |
Referencias:
- Bayer, D., Bang Le, V., De Ridder, H.N., Probe threshold and probe trivially perfect graphs (2009) Theoretical Computer Science, 410 (47-49), pp. 4812-4822
- Brown, D.E., Ludgren, J.R., Bipartite probe interval graphs, circular-arc graphs, and interval point bigraphs (2006) Australasian Journal of Combinatorics, 35, pp. 221-236
- Brown, D.E., Ludgren, J.R., Sheng, L., Characterization of cycle-free unit probe interval graphs (2009) Discrete Applied Mathematics, 157, pp. 762-767
- Chandler, D., Chang, D.-M., Kloks, T., Liu, J., Peng, S.-L., On probe permutation graphs (2009) Discrete Applied Mathematics, 157, pp. 2611-2619
- Chandler, D., Chang, M.-S., Klocks, T., Liu, J., Peng, S.-L., Recognition of probe and partitioned probe distance hereditary graphs (2006) Lecture Notes in Computer Science, 4041, pp. 267-278
- Chandler, D., Chang, M.-S., Kloks, T., Bang Le, V., Peng, S.-L., Probe ptolemaic graphs (2008) COCOON, pp. 468-477
- Chv́atal, V., Hammer, P.L., (1975) Aggregation of Inequalities in Integer Programming, , Technical Report CS-TR-75-518, Stanford University
- Giakoumakis, V., Roussel, F., Thuillier, H., On p4-tidy graphs (1997) Discrete Mathematics & Theoretical Computer Science, 1 (1), pp. 17-41
- Golumbic, M.C., Lipshteyn, M., Chordal probe graphs (2004) Discrete Applied Mathematics, 143 (1-3), pp. 221-237
- Golumbic, M.C., Trenk, A.N., (2004) Tolerance Graphs, , Cambridge University Press, New York
- Hòang, C., (1985) Perfect Graphs, , PhD thesis, School of Computer Science, McGill University, Montreal
- Jamison, B., Olariu, S., A new class of brittle graphs (1989) Studies in Applied Mathematics, 1203, pp. 89-92
- Jamison, B., Olariu, S., On a unique tree representation for p4-extendible graphs (1991) Discrete Applied Mathematics, 34, pp. 151-164
- Le, V.B., De Ridder, H.N., Probe split graphs (2007) Discrete Mathematics & Theoretical Computer Science, 9, p. 1
- Lekkerkerker, C., Boland, D., Representation of finite graphs by a set of intervals on the real line (1962) Fundamenta Mathematicae, 51, pp. 45-64
- Liu, J., Zhou, H., Dominating subgraphs in graphs with some forbidden structures (1994) Discrete Mathematics, 135, pp. 163-168
- Przulj, N., Corneil, D., 2-tree probe interval grahps have a large obstruction set (2005) Discrete Applied Mathematics, 150, pp. 216-231
- Roberts, F., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , In F. Harary, editor, Academic Press
- Sheng, L., Cycle-free probe interval graphs (1999) Congressus Numerantium, 140, pp. 33-42
- Tinhofer, G., Strong tree-cographs are birkhoff graphs (1989) Discrete Applied Mathematics, 22 (3), pp. 275-288
- Wegner, G., (1967) Eigenschaften der Nerven Homologisch-Einfacher Familien in Rn, , PhD thesis, Gottingen
- West, D.B., (2001) Introduction to Graph Theory, , Prentice Hall, New Jersey, USA, second edition
- Zhang, P., Schon, P., Fischer, E., Gayanis, E., Weiss, J., Wistler, S., Bourne, P., An algorithm based on graph theory for the assembly of contigs in physical mapping of dna (1994) Bioinformatics, 10 (3), pp. 309-317
Citas:
---------- APA ----------
Bonomo, F., Durán, G., Grippo, L.N. & Safe, M.D. (2013) . Probe interval graphs and probe unit interval graphs on superclasses of cographs. Discrete Mathematics and Theoretical Computer Science, 15(2), 177-194.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p177_Bonomo [ ]
---------- CHICAGO ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Probe interval graphs and probe unit interval graphs on superclasses of cographs" . Discrete Mathematics and Theoretical Computer Science 15, no. 2 (2013) : 177-194.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p177_Bonomo [ ]
---------- MLA ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Probe interval graphs and probe unit interval graphs on superclasses of cographs" . Discrete Mathematics and Theoretical Computer Science, vol. 15, no. 2, 2013, pp. 177-194.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p177_Bonomo [ ]
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. Probe interval graphs and probe unit interval graphs on superclasses of cographs. Discrete Math. Theor. Comput. Sci. 2013;15(2):177-194.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p177_Bonomo [ ]
