Shortness exponent (original) (raw)
In graph theory, the shortness exponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian the graphs in the family can be. Intuitively, if is the shortness exponent of a graph family , then every -vertex graph in the family has a cycle of length near but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in into a sequence , with defined to be the length of the longest cycle in graph , the shortness exponent is defined as
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, the shortness exponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian the graphs in the family can be. Intuitively, if is the shortness exponent of a graph family , then every -vertex graph in the family has a cycle of length near but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in into a sequence , with defined to be the length of the longest cycle in graph , the shortness exponent is defined as This number is always in the interval from 0 to 1; it is 1 for families of graphs that always contain a Hamiltonian or near-Hamiltonian cycle, and 0 for families of graphs in which the longest cycle length can be smaller than any constant power of the number of vertices. The shortness exponent of the polyhedral graphs is . A construction based on kleetopes shows that some polyhedral graphs have longest cycle length , while it has also been proven that every polyhedral graph contains a cycle of length . The polyhedral graphs are the graphs that are simultaneously planar and 3-vertex-connected; the assumption of 3-vertex-connectivity is necessary for these results, as there exist sets of 2-vertex-connected planar graphs (such as the complete bipartite graphs ) with shortness exponent 0. There are many additional known results on shortness exponents of restricted subclasses of planar and polyhedral graphs. The 3-vertex-connected cubic graphs (without the restriction that they be planar) also have a shortness exponent that has been proven to lie strictly between 0 and 1. (en) Показатель короткости — это числовой параметр семейства графов, который показывает, насколько далеки от гамильтоновости могут быть графы семейства. Интуитивно, если является показателем короткости графа семейства , тогда любой граф с вершинами имеет цикл длины, близкой к , но некоторые графы не имеют более длинные циклы. Более точно, для любого упорядочения графов в в последовательность , и функции , определённой как длина наибольшего цикла в графе , показатель короткости определяется как Это число всегда находится в интервале от 0 до 1. Показатель равен 1, если графы семейства всегда содержат гамильтонов или близкий к гамильтонову цикл, и 0, если наибольшая длина циклов в графах семейства может быть меньше любой постоянной степени от числа вершин. Показатель короткости полиэдральных графов равен . Построение, основанное на многогранниках Кли, показывает, что некоторые полиэдральные графы имеют наибольший цикл длиной , и было также доказано, что любой полиэдральный граф содержит цикл, длиной . Полиэдральные графы — это графы, которые одновременно являются планарными и вершинно 3-связными. Факт вершинной 3-связности здесь важен, поскольку существует множество вершинно 2-связных планарных графов (таких как полные двудольные графы ) с показателем короткости 0. Есть много дополнительных результатов относительно показателя короткости ограниченных подклассов планарных и полиэдральных графов. Вершинно 3-связные кубические графы (без требования планарности) также имеют показатель короткости, который (как было показано) лежит строго между 0 и 1. (ru) |
| dbo:wikiPageID | 51796889 (xsd:integer) |
| dbo:wikiPageLength | 3902 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032089314 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cubic_graph dbr:Complete_bipartite_graph dbr:K-vertex-connected_graph dbc:Hamiltonian_paths_and_cycles dbr:Graph_theory dbr:Hamiltonian_graph dbr:Planar_graph dbr:Kleetope dbr:Polyhedral_graph |
| dbp:wikiPageUsesTemplate | dbt:Reflist |
| dct:subject | dbc:Hamiltonian_paths_and_cycles |
| rdfs:comment | In graph theory, the shortness exponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian the graphs in the family can be. Intuitively, if is the shortness exponent of a graph family , then every -vertex graph in the family has a cycle of length near but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in into a sequence , with defined to be the length of the longest cycle in graph , the shortness exponent is defined as (en) Показатель короткости — это числовой параметр семейства графов, который показывает, насколько далеки от гамильтоновости могут быть графы семейства. Интуитивно, если является показателем короткости графа семейства , тогда любой граф с вершинами имеет цикл длины, близкой к , но некоторые графы не имеют более длинные циклы. Более точно, для любого упорядочения графов в в последовательность , и функции , определённой как длина наибольшего цикла в графе , показатель короткости определяется как (ru) |
| rdfs:label | Shortness exponent (en) Показатель короткости (ru) |
| owl:sameAs | yago-res:Shortness exponent wikidata:Shortness exponent dbpedia-hu:Shortness exponent dbpedia-ru:Shortness exponent https://global.dbpedia.org/id/2d5YN |
| prov:wasDerivedFrom | wikipedia-en:Shortness_exponent?oldid=1032089314&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Shortness_exponent |
| is dbo:wikiPageWikiLink of | dbr:Convex_Polytopes dbr:Hamiltonian_path dbr:Kleetope dbr:Polyhedral_graph |
| is foaf:primaryTopic of | wikipedia-en:Shortness_exponent |