http://dbpedia.org/ontology/abstract
|
In graph theory, a panconnected graph is a … In graph theory, a panconnected graph is an undirected graph in which, for every two vertices s and t, there exist paths from s to t of every possible length from the distance d(s,t) up to n − 1, where n is the number of vertices in the graph. The concept of panconnectivity was introduced in 1975 by Yousef Alavi and James E. Williamson. Panconnected graphs are necessarily pancyclic: if uv is an edge, then it belongs to a cycle of every possible length, and therefore the graph contains a cycle of every possible length.Panconnected graphs and are also a generalization of Hamiltonian-connected graphs (graphs that have a Hamiltonian path connecting every pair of vertices). Several classes of graphs are known to be panconnected:
* If G has a Hamiltonian cycle, then the square of G (the graph on the same vertex set that has an edge between every two vertices whose distance in G is at most two) is panconnected.
* If G is any connected graph, then the cube of G (the graph on the same vertex set that has an edge between every two vertices whose distance in G is at most three) is panconnected.
* If every vertex in an n-vertex graph has degree at least n/2 + 1, then the graph is panconnected.
* If an n-vertex graph has at least (n − 1)(n − 2)/2 + 3 edges, then the graph is panconnected.+ 3 edges, then the graph is panconnected.
|
http://dbpedia.org/ontology/wikiPageID
|
29341653
|
http://dbpedia.org/ontology/wikiPageLength
|
2383
|
http://dbpedia.org/ontology/wikiPageRevisionID
|
1056339059
|
http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Yousef_Alavi +
, http://dbpedia.org/resource/Category:Graph_families +
, http://dbpedia.org/resource/Connected_graph +
, http://dbpedia.org/resource/Pancyclic_graph +
, http://dbpedia.org/resource/Cycle_%28graph_theory%29 +
, http://dbpedia.org/resource/Undirected_graph +
, http://dbpedia.org/resource/Hamiltonian_cycle +
, http://dbpedia.org/resource/Edge_%28graph_theory%29 +
, http://dbpedia.org/resource/Path_%28graph_theory%29 +
, http://dbpedia.org/resource/Vertex_%28graph_theory%29 +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Hamiltonian_path +
|
http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Mvar +
, http://dbpedia.org/resource/Template:Math +
|
http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_families +
|
http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Graph +
|
http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Panconnectivity?oldid=1056339059&ns=0 +
|
http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Panconnectivity +
|
owl:sameAs |
http://dbpedia.org/resource/Panconnectivity +
, https://global.dbpedia.org/id/4tCrR +
, http://rdf.freebase.com/ns/m.0ds3k7_ +
, http://www.wikidata.org/entity/Q7130383 +
, http://yago-knowledge.org/resource/Panconnectivity +
|
rdf:type |
http://dbpedia.org/class/yago/Organization108008335 +
, http://dbpedia.org/ontology/Software +
, http://dbpedia.org/class/yago/SocialGroup107950920 +
, http://dbpedia.org/class/yago/Group100031264 +
, http://dbpedia.org/class/yago/Unit108189659 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/YagoPermanentlyLocatedEntity +
, http://dbpedia.org/class/yago/WikicatGraphFamilies +
, http://dbpedia.org/class/yago/YagoLegalActorGeo +
, http://dbpedia.org/class/yago/YagoLegalActor +
, http://dbpedia.org/class/yago/Family108078020 +
|
rdfs:comment |
In graph theory, a panconnected graph is a … In graph theory, a panconnected graph is an undirected graph in which, for every two vertices s and t, there exist paths from s to t of every possible length from the distance d(s,t) up to n − 1, where n is the number of vertices in the graph. The concept of panconnectivity was introduced in 1975 by Yousef Alavi and James E. Williamson. Several classes of graphs are known to be panconnected:es of graphs are known to be panconnected:
|
rdfs:label |
Panconnectivity
|