Distance-hereditary graph (original) (raw)
In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. Distance-hereditary graphs were named and first studied by , although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs.
Property | Value |
---|---|
dbo:abstract | In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. Distance-hereditary graphs were named and first studied by , although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs. It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs, but no intersection model was known until one was given by . (en) En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits. Les graphes à distance héréditaire constituent une classe de graphes d'intersection ; un modèle d'intersection a été donné par Gioan et Paul en 2012. (fr) В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф) — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе. Таким образом, любой порождённый подграф наследует расстояния большего графа. Дистанционно-наследуемые графы были названы и впервые изучались Говоркой (Howorka) , хотя для эквивалентного класса графов было уже в 1970 показано Олару и Саксом (Olaru, Sachs), что класс содержит совершенные графы. Уже некоторое время было известно, что дистанционно-наследуемые графы составляют класс графов пересечений, но модель пересечения не была известна, пока её не дали Иоан и Пауль. (ru) В теорії графів дистанційно-успадковуваний граф (або цілком сепарабельний граф) — це граф, у якому відстані в будь-якому зв'язному породженому підграфі такі самі, як і в початковому графі. Таким чином, будь-який породжений підграф успадковує відстані більшого графу. Дистанційно-успадковувані графи назвав і вперше вивчив Говорка (Howorka), хоча вже 1970 року Олару і Сакс (Olaru, Sachs) для еквівалентного класу графів показали, що клас містить досконалі графи. Вже деякий час було відомо, що дистанційно-успадковувані графи складають клас графів перетинів, але модель перехрещення не була відомою, поки її не дали Іоан і Пауль. (uk) |
dbo:thumbnail | wiki-commons:Special:FilePath/Distance-hereditary_graph.svg?width=300 |
dbo:wikiPageExternalLink | https://archive.org/details/graphclassessurv0000bran http://www.graphclasses.org/index.html https://hal-lirmm.ccsd.cnrs.fr/lirmm-00090372/file/D21.PDF http://www.graphclasses.org/classes/gc_80.html |
dbo:wikiPageID | 17315337 (xsd:integer) |
dbo:wikiPageLength | 19728 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1113519248 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Parity_graph dbc:Graph_families dbc:Perfect_graphs dbr:Path_graph dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:Ptolemaic_graph dbr:Complete_bipartite_graph dbr:Connected_graph dbr:Clique-width dbr:Graph_coloring dbr:Graph_power dbr:NP-hard dbr:Connected_dominating_set dbr:SIAM_Journal_on_Computing dbr:Chordal_bipartite_graph dbr:Shortest_path dbr:Clique_(graph_theory) dbr:Complement_graph dbr:Perfect_graph dbr:Spanning_tree dbr:Theoretical_Computer_Science_(journal) dbr:Meyniel_graph dbr:Tree_(graph_theory) dbr:Treewidth dbr:Triangle-free_graph dbr:Trivially_perfect_graph dbr:Distance dbr:Lecture_Notes_in_Computer_Science dbr:Adjacency_matrix dbr:Cycle_graph dbr:Dynamic_programming dbr:Forbidden_graph_characterization dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Discrete_mathematics dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Intersection_graph dbr:Courcelle's_theorem dbr:Chordal_graph dbr:Bipartite_graph dbr:Block_graph dbc:Intersection_classes_of_graphs dbr:Cograph dbr:Modular_graph dbr:Circle_graph dbr:Neighborhood_(graph_theory) dbr:Perfectly_orderable_graph dbr:Intersection_class_of_graphs dbr:Hamiltonian_cycle dbr:Split_decomposition dbr:File:Distance-hereditary_construction.svg dbr:File:Distance-hereditary_graph.svg |
dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:ISBN dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Sup |
dct:subject | dbc:Graph_families dbc:Perfect_graphs dbc:Intersection_classes_of_graphs |
gold:hypernym | dbr:Graph |
rdf:type | dbo:Software yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Communication100033020 yago:Graph107000195 yago:Group100031264 yago:WikicatIntersectionClassesOfGraphs yago:VisualCommunication106873252 yago:WikicatPerfectGraphs |
rdfs:comment | In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. Distance-hereditary graphs were named and first studied by , although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs. (en) En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits. (fr) В теорії графів дистанційно-успадковуваний граф (або цілком сепарабельний граф) — це граф, у якому відстані в будь-якому зв'язному породженому підграфі такі самі, як і в початковому графі. Таким чином, будь-який породжений підграф успадковує відстані більшого графу. Дистанційно-успадковувані графи назвав і вперше вивчив Говорка (Howorka), хоча вже 1970 року Олару і Сакс (Olaru, Sachs) для еквівалентного класу графів показали, що клас містить досконалі графи. (uk) В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф) — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе. Таким образом, любой порождённый подграф наследует расстояния большего графа. Дистанционно-наследуемые графы были названы и впервые изучались Говоркой (Howorka) , хотя для эквивалентного класса графов было уже в 1970 показано Олару и Саксом (Olaru, Sachs), что класс содержит совершенные графы. (ru) |
rdfs:label | Distance-hereditary graph (en) Graphe à distance héréditaire (fr) Дистанционно-наследуемый граф (ru) Дистанційно-успадковуваний граф (uk) |
owl:sameAs | freebase:Distance-hereditary graph yago-res:Distance-hereditary graph wikidata:Distance-hereditary graph dbpedia-fr:Distance-hereditary graph dbpedia-hu:Distance-hereditary graph dbpedia-ru:Distance-hereditary graph dbpedia-uk:Distance-hereditary graph https://global.dbpedia.org/id/4j31D |
prov:wasDerivedFrom | wikipedia-en:Distance-hereditary_graph?oldid=1113519248&ns=0 |
foaf:depiction | wiki-commons:Special:FilePath/Distance-hereditary_construction.svg wiki-commons:Special:FilePath/Distance-hereditary_graph.svg |
foaf:isPrimaryTopicOf | wikipedia-en:Distance-hereditary_graph |
is dbo:wikiPageRedirects of | dbr:Completely_separable_graph |
is dbo:wikiPageWikiLink of | dbr:Parity_graph dbr:Pathwidth dbr:Induced_path dbr:Induced_subgraph dbr:Lexicographic_breadth-first_search dbr:Ptolemaic_graph dbr:Clique-width dbr:Chordal_bipartite_graph dbr:Clique_cover dbr:Perfect_graph dbr:Split_(graph_theory) dbr:Meyniel_graph dbr:Minimum_routing_cost_spanning_tree dbr:Chordal_graph dbr:Block_graph dbr:Cograph dbr:Modular_decomposition dbr:Modular_graph dbr:Circle_graph dbr:Greedy_coloring dbr:Implicit_graph dbr:Longest_path_problem dbr:Completely_separable_graph dbr:Perfectly_orderable_graph dbr:Twin-width |
is foaf:primaryTopic of | wikipedia-en:Distance-hereditary_graph |