China 
Africa 
Explore chapters and articles related to this topic
Essential properties of the Tutte polynomial
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
One of the best known open questions relating to specific values of the Tutte polynomial is Tutte's 5-flow conjecture from [1092]. Tutte showed that if a graph G has a nowhere-zero n-flow, then it has a nowhere-zero (n+1) -flow. He noted that the four color theorem (conjecture at that time) is equivalent to the statement that every bridgeless planar graph has a nowhere-zero 4-flow. Without the condition of planarity this is not true (the Petersen graph is a counterexample). However, Tutte conjectured that every bridgeless graph G, planar or not, has a nowhere-zero 5-flow, i.e., has T(G;0,−4)≠0. This conjecture has remained open for over 60 years, despite substantial progress by Jaeger [644, 645] and Seymour [999], who proved that the answer for 8-flows and 6-flows respectively is yes. In Section 7 of [1094], Tutte also conjectured (in algebraic language) that if G is bridgeless and does not have the Petersen graph as a minor, then G has a nowhere-zero 4-flow; this is also open.
Introduction to Graph Theory
Published in Sriraman Sridharan, R. Balakrishnan, Foundations of Discrete Mathematics with Algorithms and Programming, 2019
Sriraman Sridharan, R. Balakrishnan
Minor of a graphA minor of a simple graph G is any graph obtainable from G by a sequence of vertex deletions, edge deletions and edge contractions (in any order).[Minor of a graph] As an example, consider again the Petersen graph. The complete graph on 5 vertices K5 $ K_5 $ is a minor of the Petersen graph, because K5 $ K_5 $ is obtained by contracting the five edges joining the pentagon (the elementary cycle (1, 2, 3, 4, 5, 1) and the pentagram (the elementary cycle (6, 8, 10, 7, 9, 6) (see the Petersen graph drawn in the text). Hence by the following theorem, the Petersen graph is nonplanar.
Hamilton Cycles
Published in Kenneth H. Rosen, Graphs, Algorithms, and Optimization, 2005
The Petersen graph is also non-hamiltonian, but this cannot be proved using Lemma 9.1. Instead we use an exhaustive search method called the multi-path method, see Rubin [105]. Suppose that C were a hamilton cycle in the Petersen graph G, as shown in Figure 9.4. G is composed of an outer and inner pentagon, joined by a perfect matching. Since C uses exactly two edges at each vertex of G, it follows that C must use at least three edges of the outer pentagon, for otherwise some vertex on it would be missed by G. Consequently, C uses two adjacent edges of the outer pentagon. Without loss of generality, suppose that it uses the edges uv and vw. This means that G does not use the edge vy, so we can delete it from G. Deleting vy reduces the degree of y to two, so that now both remaining edges at y must be part of C. So the two paths (u, v, w) and (x, y, z) must be part of C, where a path is denoted by a sequence of vertices. This is illustrated in Figure 9.4.
The Garden of Eden theorem for cellular automata on group sets
Published in International Journal of Parallel, Emergent and Distributed Systems, 2019
According to Corollary 6.8, there is no subgroup of that acts freely and transitively on by . And, according to Lemma 6.2 and the note above, the space is right amenable if and only if the group G is amenable. For example:If G is the integer lattice and is the Petersen graph, then is right amenable.If G is the free group over , where and is the Coxeter graph, then is not right amenable.
Embedding spanning disjoint cycles in augmented cube networks with prescribed vertices in each cycle
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Weiyan Wu, Eminjan Sabir, Hongwei Qiao
In view of the fact that no genuinely useful characterization of spanning cycles exists or seems likely to be found, a good deal of effort has been devoted to developing sufficient conditions for a graph to be spanning cyclable. Chronologically, in [12] and [13], the authors independently provided a minimum degree sufficient conditions for a graph to be spanning k-cyclable. The problem of spanning k-cyclability of general graphs is well studied in the literature, see the survey article [14,15]. Besides, there are some results on spanning cyclability of special graph families. Lin etal. proved that the hypercube with is spanning k-cyclable for [9], and Kung etal. showed that the crossed cube is spanning k-cyclable for [16]. Shinde and Borse proved that the n-dimensional tori is spanning k-cyclable for [11]. Yang and Hsu proved that the generalized Petersen graph is spanning 2-cyclable for [10]. Recently, Qiao etal. proved that the enhanced hypercube with is spanning k-cyclable for and with n = 2, 3 is spanning k-cyclable for [4]. Qiao etal. also proved that Cayley graph is spanning k-cyclable if and [17].