共查询到20条相似文献,搜索用时 31 毫秒
1.
We adapt the cycle space of a finite graph to locally
finite infinite graphs, using as infinite cycles the
homeomorphic images of the unit circle S1 in the
graph compactified by its ends. We prove that this cycle space
consists of precisely the sets of edges that meet every finite
cut evenly, and that the spanning trees whose fundamental cycles
generate this cycle space are precisely the end-faithful
spanning trees. We also generalize Eulers theorem by showing
that a locally finite connected graph with ends contains a
closed topological curve traversing every edge exactly once if
and only if its entire edge set lies in this cycle space.To the memory of C. St. J. A.
Nash-Williams 相似文献
2.
We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite
graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation
of the cycles in a finite graph as its 2-regular connected subgraphs. 相似文献
3.
In a finite graph, an edge set Z is an element of the cycle space if and only if every vertex has even degree in Z. We extend this basic result to the topological cycle space, which allows infinite circuits, of locally finite graphs. In
order to do so, it becomes necessary to attribute a parity to the ends of the graph. 相似文献
4.
Xingxing Yu 《Journal of Graph Theory》2006,53(3):173-195
Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for graphs with infinitely many vertex disjoint dividing cycles. A cycle in an infinite plane graph is called dividing if both regions of the plane bounded by this cycle contain infinitely many vertices of the graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 173–195, 2006 相似文献
5.
A. Georgakopoulos 《Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg》2006,76(1):235-245
We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These
graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture
that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected. 相似文献
6.
Norbert Seifter 《Combinatorica》1984,4(4):351-356
LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a
known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section
we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2). 相似文献
7.
We show that the cover-index of an infinite graph can be expressed in terms of colouring properties of its finite subgraphs when the minimum degree of the graph is finite. We prove that every simple graph with infinite minimum degree contains a tree which is regular of degree and use this to prove that every graph with minimum degree can be decomposed into mutually edge-disjoint spanning subgraphs without ioslated vertices. In particular, the cover-index of a graph equals the minimum degree, when this is infinite. 相似文献
8.
Carsten Thomassen 《Journal of Combinatorial Theory, Series B》1980,29(2):244-271
We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs. 相似文献
9.
G has property if whenever F and H are connected graphs with and |H|=|F|+1, and and are isometric embeddings, then there is an isometric embedding such that . It is easy to construct an infinite graph with for all k, and holds in almost all finite graphs. Prior to this work, it was not known whether there exist any finite graphs with . We show that the Johnson graphs J(n,3) satisfy whenever , and that J(6,3) is the smallest graph satisfying . We also construct finite graphs satisfying and local versions of the extension axioms studied in connection with the Rado universal graph.
Received June 9, 1998 相似文献
10.
Graph-like continua provide a very natural setting for generalizing finite graphs to infinite, compact structures. For example, the Freudenthal compactification of a locally finite graph, exploited by Diestel and his students in their study of the cycle space of an infinite graph, is an example of a graph-like continuum. Generalizing earlier works in special cases, the authors, along with Christian, have proved MacLane’s and Whitney’s characterizations of planarity for graph-like continua (Electron. J. Combin. 17 (2010)). In this work, we consider embeddings of graph-like continua in compact surfaces and show that: (i) every edge is in an open disc that meets the graph-like continuum precisely in that edge; (ii) there are natural analogues of face boundary walks; (iii) there is a graph-like continuum triangulating the same surface and containing as a sub-graphlike continuum the original embedded graph-like continuum; (iv) the face boundaries generate a subspace of the cycle space; and (v) the quotient of the cycle space by the boundary cycles is the homology of the surface. These all generalize results known for embeddings of finite graphs. 相似文献
11.
《Optimization》2012,61(4-5):441-458
We consider the Hamiltonian cycle problem (HCP) embedded in a singularly perturbed Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of long-run state-action frequencies induced by the MDP's stationary policies. We also consider two quadratic functionals over the same space. We show that when the perturbation parameter, ? is sufficiently small the Hamiltonian cycles of the given directed graph are precisely the maximizers of one of these quadratic functionals over the frequency space intersected with an appropriate (single) contour of the second quadratic functional. In particular, all these maximizers have a known Euclidean distance of z m (?) from the origin. Geometrically, this means that Hamiltonian cycles, if any, are the points in the frequency polytope where the circle of radius z m (?) intersects a certain ellipsoid. 相似文献
12.
A graph is one‐ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one‐ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree‐decomposition such that the decomposition tree is one‐ended and the tree‐decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one‐ended graph contains an infinite family of pairwise disjoint rays. 相似文献
13.
A graph G is
inexhaustible if whenever a vertex of G is deleted the remaining graph is
isomorphic to G. We address a
question of Cameron [6], who asked which countable graphs are
inexhaustible. In particular, we prove that there are continuum
many countable inexhaustible graphs with properties in common
with the infinite random graph, including adjacency properties
and universality. Locally finite inexhaustible graphs and
forests are investigated, as is a semigroup structure on the
class of inexhaustible graphs. We extend a result of [7] on
homogeneous inexhaustible graphs to pseudo-homogeneous
inexhaustible graphs.The authors gratefully acknowledge support from the
Natural Science and Engineering Research Council of Canada
(NSERC). 相似文献
14.
Wesley Pegden 《Combinatorica》2006,26(5):577-585
We prove that the out-distance sequence {f+(k)} of a vertex-transitive digraph of finite or infinite degree satisfies f+(k+1)≤f+(k)2 for k≥1, where f+(k) denotes the number of vertices at directed distance k from a given vertex. As a corollary, we prove that for a connected vertex-transitive undirected graph of infinite degree
d, we have f(k)=d for all k, 1≤k<diam(G). This answers a question by L. Babai. 相似文献
15.
Karen Seyffarth 《Combinatorica》1993,13(4):477-482
Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn–1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs. 相似文献
16.
Constructing even radius tightly attached half-arc-transitive graphs of valency four 总被引:1,自引:1,他引:0
A finite graph X is half-arc-transitive if its automorphism group is transitive on vertices and edges, but not on arcs. When X is tetravalent, the automorphism group induces an orientation on the edges and a cycle of X is called an alternating cycle if its consecutive edges in the cycle have opposite orientations. All alternating cycles of X have the same length and half of this length is called the radius of X. The graph X is said to be tightly attached if any two adjacent alternating cycles intersect in the same number of vertices equal to the radius of X. Marušič (J. Comb. Theory B, 73, 41–76, 1998) classified odd radius tightly attached tetravalent half-arc-transitive graphs. In this paper, we classify the half-arc-transitive
regular coverings of the complete bipartite graph K
4,4 whose covering transformation group is cyclic of prime-power order and whose fibre-preserving group contains a half-arc-transitive
subgroup. As a result, two new infinite families of even radius tightly attached tetravalent half-arc-transitive graphs are
constructed, introducing the first infinite families of tetravalent half-arc-transitive graphs of 2-power orders.
相似文献
17.
M. Ajtai 《Combinatorica》1994,14(4):379-416
We present an algorithm which inn
3 (logn)3 time constructs a 3-regular expander graph onn vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of lengths=clogn decreases (for some fixed absolute constantc). When we reach a local minimum in the number of cycles of lengths the graph is an expander. 相似文献
18.
For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R(n), which we name the infinite random n‐ordered graphs. The graphs R(n) play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R(n) as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R(n) are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R(n). © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009 相似文献
19.
N. Polat 《Periodica Mathematica Hungarica》1993,27(2):125-136
It is shown that ifG is a graph which is contractible or dismantlable or finitely ball-Helly, and without infinite paths; or which is bounded, finitely ball-Helly and without infinite simplices then: (i) any contraction ofG stabilizes a finite simplex; and (ii)G contains a finite simplex which is invariant under any automorphism. 相似文献
20.
We characterize the fundamental group of a locally finite graph G with ends combinatorially, as a group of infinite words. Our characterization gives rise to a canonical embedding of this group in the inverse limit of the free groups π1(G′) with G′⊆G finite. 相似文献