Graph of constant finite eccentricity: Difference between revisions
(Created page with "{{undirected graph property}} ==Definition== Suppose <math>G</math> is a connected undirected graph. We say that <math>G</math> is a '''graph of cons...") |
No edit summary |
||
| Line 7: | Line 7: | ||
# <math>G</matH> is a [[graph of finite diameter]] and its [[defining ingredient::radius of a graph|radius]] equals its [[defining ingredient::diameter of a graph|diameter]]. | # <math>G</matH> is a [[graph of finite diameter]] and its [[defining ingredient::radius of a graph|radius]] equals its [[defining ingredient::diameter of a graph|diameter]]. | ||
# The [[eccentricity of a vertex|eccentricity]] of every vertex of <math>G</math> is equal to a fixed finite number. | # The [[eccentricity of a vertex|eccentricity]] of every vertex of <math>G</math> is equal to a fixed finite number. | ||
==Relation with other properties== | |||
===Stronger properties=== | |||
{| class="sortable" border="1" | |||
! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions | |||
|- | |||
| [[Weaker than::vertex-transitive finite connected graph]] || || || || | |||
|- | |||
| [[Weaker than::vertex-transitive graph of finite diameter]] || || || || | |||
|} | |||
===Weaker properties=== | |||
{| class="sortable" border="1" | |||
! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions | |||
|- | |||
| [[Stronger than::connected graph]] || || || || | |||
|} | |||
Latest revision as of 17:48, 28 May 2012
This article defines a property that can be evaluated to true/false for any undirected graph, and is invariant under graph isomorphism. Note that the term "undirected graph" as used here does not allow for loops or parallel edges, so there can be at most one edge between two distinct vertices, the edge is completely described by the vertices it joins, and there can be no edge from a vertex to itself.
View other such properties
Definition
Suppose is a connected undirected graph. We say that is a graph of constant finite eccentricity if it satisfies the following equivalent conditions:
- is a graph of finite diameter and its radius equals its diameter.
- The eccentricity of every vertex of is equal to a fixed finite number.
Relation with other properties
Stronger properties
| Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
|---|---|---|---|---|
| vertex-transitive finite connected graph | ||||
| vertex-transitive graph of finite diameter |
Weaker properties
| Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
|---|---|---|---|---|
| connected graph |