Probe interval graphs and probe unit interval graphs on superclasses of cographs

Mostrar todas las versiones(2)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D.
Formato: JOUR
Materias:
Forbidden induced subgraphs
P4-tidy graphs
Probe interval graphs
Probe unit interval graphs
Treecographs
Human Genome Project
Interval graph
Physical mapping
Probe intervals
Unit interval graphs
Forestry
Graphic methods
Probes
Trees (mathematics)
Mathematics
Trees
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_14627264_v15_n2_p177_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_14627264_v15_n2_p177_Bonomo
record_format dspace
spelling todo:paper_14627264_v15_n2_p177_Bonomo2023-10-03T16:16:38Z Probe interval graphs and probe unit interval graphs on superclasses of cographs Bonomo, F. Durán, G. Grippo, L.N. Safe, M.D. 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 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. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Grippo, L.N. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_14627264_v15_n2_p177_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
spellingShingle 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
Bonomo, F.
Durán, G.
Grippo, L.N.
Safe, M.D.
Probe interval graphs and probe unit interval graphs on superclasses of cographs
topic_facet 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
description 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.
format JOUR
author Bonomo, F.
Durán, G.
Grippo, L.N.
Safe, M.D.
author_facet Bonomo, F.
Durán, G.
Grippo, L.N.
Safe, M.D.
author_sort Bonomo, F.
title Probe interval graphs and probe unit interval graphs on superclasses of cographs
title_short Probe interval graphs and probe unit interval graphs on superclasses of cographs
title_full Probe interval graphs and probe unit interval graphs on superclasses of cographs
title_fullStr Probe interval graphs and probe unit interval graphs on superclasses of cographs
title_full_unstemmed Probe interval graphs and probe unit interval graphs on superclasses of cographs
title_sort probe interval graphs and probe unit interval graphs on superclasses of cographs
url http://hdl.handle.net/20.500.12110/paper_14627264_v15_n2_p177_Bonomo
work_keys_str_mv AT bonomof probeintervalgraphsandprobeunitintervalgraphsonsuperclassesofcographs
AT durang probeintervalgraphsandprobeunitintervalgraphsonsuperclassesofcographs
AT grippoln probeintervalgraphsandprobeunitintervalgraphsonsuperclassesofcographs
AT safemd probeintervalgraphsandprobeunitintervalgraphsonsuperclassesofcographs
_version_ 1807314674215026688

Ejemplares similares