Distance-hereditary graph (original) (raw)

About DBpedia

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.

thumbnail

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