Search

In this paper we investigate orders, longest cycles and the number of cycles of automorphisms of finite vertex-transitive graphs. In particular, we show that the order of every automorphism of a connected vertex-transitive graph with n vertices and of valence d , d ≤ 4 , is at most c d n where c 3 = 1 and c 4 = 9. Whether such a constant c d exists for valencies larger than 4 remains an unanswered question. Further, we prove that every automorphism g of a finite connected 3-valent vertex-transitive graph Γ, Γ ≇ K 3 , 3 , has a regular orbit, that is, an orbit of 〈 g 〉 of length equal to the order of g. Moreover, we prove that in this case either Γ belongs to a well understood family of exceptional graphs or at least 5/12 of the vertices of Γ belong to a regular orbit of g. Finally, we give an upper bound on the number of orbits of a cyclic group of automorphisms C of a connected 3-valent vertex-transitive graph Γ in terms of the number of vertices of Γ and the length of a longest orbit of C. [ABSTRACT FROM AUTHOR]

Ellis, Filmus, and Friedgut proved an old conjecture of Simonovits and Sós showing that any triangle-intersecting family of graphs on n vertices has size at most 2 ( n 2 ) − 3 , with equality for the family of graphs containing some fixed triangle. They conjectured that their results extend to cross-intersecting families, as well to K t -intersecting families. We prove these conjectures for t ∈ { 3 , 4 } , showing that if F 1 and F 2 are families of graphs on n labeled vertices such that for any G 1 ∈ F 1 and G 2 ∈ F 2 , G 1 ∩ G 2 contains a K t , then | F 1 | | F 2 | ≤ 4 ( n 2 ) − ( t 2 ) , with equality if and only if F 1 = F 2 consists of all graphs that contain some fixed K t. We also establish a stability result. More generally, " G 1 ∩ G 2 contains a K t " can be replaced by " G 1 and G 2 agree on a non- (t − 1) -colorable graph." [ABSTRACT FROM AUTHOR]

Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. However, for each fixed finite field F , the list needs to contain only finitely many F -representable matroids, due to the well-quasi-ordering of F -representable matroids of bounded branch-width under taking matroid minors [J.F. Geelen, A.M.H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these F -representable excluded minors in general. We consider the class of matroids of path-width at most k for fixed k. We prove that for a finite field F , every F -representable excluded minor for the class of matroids of path-width at most k has at most 2 | F | O (k 2) elements. We can therefore compute, for any integer k and a fixed finite field F , the set of F -representable excluded minors for the class of matroids of path-width k , and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an F -represented matroid is at most k. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most k has at most 2 2 O (k 2) vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs. [ABSTRACT FROM AUTHOR]

The topic is the average order of a connected induced subgraph of a graph. This generalizes, to graphs in general, the average order of a subtree of a tree. In 1983, Jamison proved that the average order of a subtree, over all trees of order n , is minimized by the path P n. In 2018, Kroeker, Mol, and Oellermann conjectured that P n minimizes the average order of a connected induced subgraph over all connected graphs. The main result of this paper confirms this conjecture. [ABSTRACT FROM AUTHOR]

We prove that every graph has a canonical tree of tree-decompositions that distinguishes all principal tangles (these include the ends and various kinds of large finite dense structures) efficiently. Here 'trees of tree-decompositions' are a slightly weaker notion than 'tree-decompositions' but much more well-behaved than 'tree-like metric spaces'. This theorem is best possible in the sense that we give an example that 'trees of tree-decompositions' cannot be strengthened to 'tree-decompositions' in the above theorem. This implies results of Dunwoody and Krön as well as of Carmesin, Diestel, Hundertmark and Stein. Beyond that for locally finite graphs our result gives for each k ∈ N canonical tree-decompositions that distinguish all k -distinguishable ends efficiently. [ABSTRACT FROM AUTHOR]

We disprove a conjecture of Frank [3] stating that each weakly 2 k -connected graph has a k -vertex-connected orientation. For k ≥ 3 , we also prove that the problem of deciding whether a graph has a k -vertex-connected orientation is NP-complete. [ABSTRACT FROM AUTHOR]

Let G be a 3-connected graph with a 3-connected (or sufficiently small) simple minor H. We establish that G has a forest F with at least ⌈ (| G | − | H | + 1) / 2 ⌉ edges such that G / e is 3-connected with an H -minor for each e ∈ E (F). Moreover, we may pick F with | G | − | H | edges provided G is triangle-free. These results are sharp. Our result generalizes a previous one by Ando et al., which establishes that a 3-connected graph G has at least ⌈ | G | / 2 ⌉ contractible edges. As another consequence, each triangle-free 3-connected graph has an spanning tree of contractible edges. Our results follow from a more general theorem on graph minors, a splitter theorem, which is also established here. [ABSTRACT FROM AUTHOR]

The fractional arboricity of a graph G , denoted by γ f ( G ) , is defined as γ f ( G ) = max H ⊆ G , v ( H ) > 1 ⁡ e ( H ) v ( H ) − 1 . The famous Nash-Williams' Theorem states that a graph G can be partitioned into at most k forests if and only if γ f ( G ) ≤ k . A graph is d -bounded if it has maximum degree at most d . The Nine Dragon Tree (NDT) Conjecture [posed by Montassier, Ossona de Mendez, Raspaud, and Zhu, at [11] ] asserts that if γ f ( G ) ≤ k + d k + d + 1 , then G decomposes into k + 1 forests with one being d -bounded. In this paper, it is proven that the Nine Dragon Tree Conjecture is true for all the cases in which d = 1 . [ABSTRACT FROM AUTHOR]

Jørgensen conjectured that every 6-connected graph with no K 6 minor has a vertex whose deletion makes the graph planar. We prove the conjecture for all sufficiently large graphs. [ABSTRACT FROM AUTHOR]

We give an elementary and self-contained proof, and a numerical improvement, of a weaker form of the excluded clique minor theorem of Robertson and Seymour, the following. Let t , r ≥ 1 be integers, and let R = 49152 t 24 ( 40 t 2 + r ) . An r -wall is obtained from a 2 r × r -grid by deleting every odd vertical edge in every odd row and every even vertical edge in every even row, then deleting the two resulting vertices of degree one, and finally subdividing edges arbitrarily. The vertices of degree two that existed before the subdivision are called the pegs of the r -wall. Let G be a graph with no K t minor, and let W be an R -wall in G . We prove that there exist a set A ⊆ V ( G ) of size at most 12288 t 24 and an r -subwall W ′ of W such that V ( W ′ ) ∩ A = ∅ and W ′ is a flat wall in G − A in the following sense. There exists a separation ( X , Y ) of G − A such that X ∩ Y is a subset of the vertex set of the cycle C ′ that bounds the outer face of W ′ , V ( W ′ ) ⊆ Y , every peg of W ′ belongs to X and the graph G [ Y ] can almost be drawn in the unit disk with the vertices X ∩ Y drawn on the boundary of the disk in the order determined by C ′ . Here almost means that the assertion holds after repeatedly removing parts of the graph separated from X ∩ Y by a cutset Z of size at most three, and adding all edges with both ends in Z . Our proof gives rise to an algorithm that runs in polynomial time even when r and t are part of the input instance. The proof is self-contained in the sense that it uses only results whose proofs can be found in textbooks. [ABSTRACT FROM AUTHOR]

We give a new proof of Steinitz's classical theorem in the case of plane triangulations, which allows us to obtain a new general bound on the grid size of the simplicial polytope realizing a given triangulation, subexponential in a number of special cases. Formally, we prove that every plane triangulation G with n vertices can be embedded in R 2 in such a way that it is the vertical projection of a convex polyhedral surface. We show that the vertices of this surface may be placed in a 4 n 3 × 8 n 5 × ζ ( n ) integer grid, where ζ ( n ) ≤ ( 500 n 8 ) τ ( G ) and τ ( G ) denotes the shedding diameter of G , a quantity defined in the paper. [ABSTRACT FROM AUTHOR]

A k -edge-colored graph is a finite, simple graph with edges labeled by numbers 1 , … , k . A function from the vertex set of one k -edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k -edge-colored graph H (not necessarily with the underlying graph in F ) is k -universal for F when any k -edge-colored graph with the underlying graph in F admits a homomorphism to H . We characterize graph classes that admit k -universal graphs. For such classes, we establish asymptotically almost tight bounds on the size of the smallest universal graph. For a nonempty graph G , the density of G is the maximum ratio of the number of edges to the number of vertices ranging over all nonempty subgraphs of G . For a nonempty class F of graphs, D ( F ) denotes the density of F , that is the supremum of densities of graphs in F . The main results are the following. The class F admits k -universal graphs for k ⩾ 2 if and only if there is an absolute constant that bounds the acyclic chromatic number of any graph in F . For any such class, there exists a constant c , such that for any k ⩾ 2 , the size of the smallest k -universal graph is between k D ( F ) and c k ⌈ D ( F ) ⌉ . A connection between the acyclic coloring and the existence of universal graphs was first observed by Alon and Marshall (1998) [2] . One of their results is that for the class of planar graphs, the size of the smallest k -universal graph is between k 3 + 3 and 5 k 4 . Our results yield that there exists a constant c such that for all k , this size is bounded from above by c k 3 . [ABSTRACT FROM AUTHOR]

We extend to infinite graphs the matroidal characterization of finite graph duality, that two graphs are dual iff they have complementary spanning trees in some common edge set. The naive infinite analogue of this fails. The key in an infinite setting is that dual trees must share between them not only the edges of their host graphs but also their ends: the statement that a set of edges is acyclic and connects all the vertices in one of the graphs iff the remaining edges do the same in its dual will hold only once each of the two graphs' common ends has been assigned to one graph but not the other, and ‘cycle’ and ‘connected’ are interpreted topologically in the space containing the respective edges and precisely the ends thus assigned. This property characterizes graph duality: if, conversely, the spanning trees of two infinite graphs are complementary in this end-sharing way, the graphs form a dual pair. [ABSTRACT FROM AUTHOR]

A k - block in a graph G is a maximal set of at least k vertices no two of which can be separated in G by removing less than k vertices. It is separable if there exists a tree-decomposition of adhesion less than k of G in which this k -block appears as a part. Carmesin et al. proved that every finite graph has a canonical tree-decomposition of adhesion less than k that distinguishes all its k -blocks and tangles of order k . We construct such tree-decompositions with the additional property that every separable k -block is equal to the unique part in which it is contained. This proves a conjecture of Diestel. [ABSTRACT FROM AUTHOR]

Almost 4 -connectivity is a weakening of 4-connectivity which allows for vertices of degree three. In this paper we prove the following theorem. Let G be an almost 4-connected triangle-free planar graph, and let H be an almost 4-connected non-planar graph such that H has a subgraph isomorphic to a subdivision of G . Then there exists a graph G ′ such that G ′ is isomorphic to a minor of H , and either (i) G ′ = G + u v for some vertices u , v ∈ V ( G ) such that no facial cycle of G contains both u and v , or (ii) G ′ = G + u 1 v 1 + u 2 v 2 for some distinct vertices u 1 , u 2 , v 1 , v 2 ∈ V ( G ) such that u 1 , u 2 , v 1 , v 2 appear on some facial cycle of G in the order listed. This is a lemma to be used in other papers. In fact, we prove a more general theorem, where we relax the connectivity assumptions, do not assume that G is planar, and consider subdivisions rather than minors. Instead of face boundaries we work with a collection of cycles that cover every edge twice and have pairwise connected intersection. Finally, we prove a version of this result that applies when G \ X is planar for some set X ⊆ V ( G ) of size at most k , but H \ Y is non-planar for every set Y ⊆ V ( H ) of size at most k . [ABSTRACT FROM AUTHOR]

In Part I of this series we described three algorithms that construct canonical tree-decompositions of graphs which distinguish all their k -blocks and tangles of order k . We now establish lower bounds on the number of parts in these decompositions that contain such a block or tangle, and determine conditions under which such parts contain nothing but a k -block. [ABSTRACT FROM AUTHOR]

We construct tree-decompositions of graphs that distinguish all their k -blocks and tangles of order k , for any fixed integer k . We describe a family of algorithms to construct such decompositions, seeking to maximize their diversity subject to the requirement that they commute with graph isomorphisms. In particular, all the decompositions constructed are invariant under the automorphisms of the graph. [ABSTRACT FROM AUTHOR]

For any integer k ≥ 0 , let ξ k be the supremum in ( 1 , 2 ] such that the flow polynomial F ( G , λ ) has no real roots in ( 1 , ξ k ) for all graphs G with at most k vertices of degrees larger than 3. We prove that ξ k can be determined by considering a finite set of graphs and show that ξ k = 2 for k ≤ 2 , ξ 3 = 1.430 ⋯  , ξ 4 = 1.361 ⋯ and ξ 5 = 1.317 ⋯  . [ABSTRACT FROM AUTHOR]

Let G be a plane graph with outer cycle C , let v 1 , v 2 ∈ V ( C ) and let ( L ( v ) : v ∈ V ( G ) ) be a family of sets such that | L ( v 1 ) | = | L ( v 2 ) | = 2 , | L ( v ) | ≥ 3 for every v ∈ V ( C ) ∖ { v 1 , v 2 } and | L ( v ) | ≥ 5 for every v ∈ V ( G ) ∖ V ( C ) . We prove a conjecture of Hutchinson that G has a (proper) coloring ϕ such that ϕ ( v ) ∈ L ( v ) for every v ∈ V ( G ) . We will use this as a lemma in subsequent papers. [ABSTRACT FROM AUTHOR]

The arboricity of a graph G is the minimum number of colours needed to colour the edges of G so that every cycle gets at least two colours. Given a positive integer p , we define the generalized p -arboricity Arb p ( G ) of a graph G as the minimum number of colours needed to colour the edges of a multigraph G in such a way that every cycle C gets at least min ⁡ ( | C | , p + 1 ) colours. In the particular case where G has girth at least p + 1 , Arb p ( G ) is the minimum size of a partition of the edge set of G such that the union of any p parts induces a forest. In this paper, we relate the generalized p -arboricity of a graph G to the maximum density of a multigraphs having a shallow subdivision (where edges are becoming paths of length at most p ) as a subgraph of G , by proving that each of these values is bounded by a polynomial function of the other. [ABSTRACT FROM AUTHOR]

Abstract: Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least distinct 3-colorings. We show that it has at least distinct 3-colorings. [Copyright &y& Elsevier]

Abstract: We find zero-free regions in the complex plane at large for the multivariate Tutte polynomial (also known in statistical mechanics as the Potts-model partition function) of a graph G with general complex edge weights . This generalizes a result of Sokal (2001) [28] that applies only within the complex antiferromagnetic regime . Our proof uses the polymer-gas representation of the multivariate Tutte polynomial together with the Penrose identity. [Copyright &y& Elsevier]

Abstract: In 1970, Havel asked if each planar graph with the minimum distance, , between triangles large enough is 3-colorable. There are 4-chromatic planar graphs with (Aksenov, Melʼnikov, and Steinberg, 1980). The first result in the positive direction of Havelʼs problem was made in 2003 by Borodin and Raspaud, who proved that every planar graph with and no 5-cycles is 3-colorable. Recently, Havelʼs problem was solved by Dvořák, Králʼ and Thomas in the positive, which means that there exists a constant d such that each planar graph with is 3-colorable. (As far as we can judge, this d is very large.) We conjecture that the strongest possible version of Havelʼs problem (SVHP) is true: every planar graph with is 3-colorable. In this paper we prove that each planar graph with and without 5-cycles adjacent to triangles is 3-colorable. The readers are invited to prove a stronger theorem: every planar graph with and without 4-cycles adjacent to triangles is 3-colorable, which could possibly open way to proving SVHP. [Copyright &y& Elsevier]

Abstract: A classic theorem of Erdős and Pósa states that there exists a constant c such that for all positive integers k and graphs G, either G contains k vertex disjoint cycles, or there exists a subset of at most vertices intersecting every cycle of G. We consider the following generalization of the problem: fix a subset S of vertices of G. An S-cycle is a cycle containing at least one vertex of S. We show that again there exists a constant such that G either contains k disjoint S-cycles, or there exists a set of at most vertices intersecting every S-cycle. The proof yields an algorithm for finding either the disjoint S-cycles or the set of vertices intersecting every S-cycle. An immediate consequence is an -approximation algorithm for finding disjoint S-cycles. [Copyright &y& Elsevier]

Abstract: We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list. [Copyright &y& Elsevier]

Abstract: It is well known that the spectral radius of a tree whose maximum degree is Δ cannot exceed . A similar upper bound holds for arbitrary planar graphs, whose spectral radius cannot exceed , and more generally, for all d-degenerate graphs, where the corresponding upper bound is . Following this, we say that a graph G is spectrally d-degenerate if every subgraph H of G has spectral radius at most . In this paper we derive a rough converse of the above-mentioned results by proving that each spectrally d-degenerate graph G contains a vertex whose degree is at most (if ). It is shown that the dependence on Δ in this upper bound cannot be eliminated, as long as the dependence on d is subexponential. It is also proved that the problem of deciding if a graph is spectrally d-degenerate is co-NP-complete. [Copyright &y& Elsevier]

Abstract: A 2-cell embedding of a graph G into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags – mutually incident vertex–edge–face triples. In this paper, we classify the regular embeddings of complete bipartite graphs into nonorientable surfaces. Such a regular embedding of exists only when n is of the form where the are primes congruent to ±1 mod 8. In this case, up to isomorphism the number of those regular embeddings of is . [Copyright &y& Elsevier]

Abstract: Let H be a graph. If G is an n-vertex simple graph that does not contain H as a minor, what is the maximum number of edges that G can have? This is at most linear in n, but the exact expression is known only for very few graphs H. For instance, when H is a complete graph , the “natural” conjecture, , is true only for and wildly false for large t, and this has rather dampened research in the area. Here we study the maximum number of edges when H is the complete bipartite graph . We show that in this case, the analogous “natural” conjecture, , is (for all ) the truth for infinitely many n. [Copyright &y& Elsevier]

Abstract: In this paper 1 [1] This article is a revised version of Daneshgar and Hajiabolhassan (2008) distributed on arXiv.org (1''st, Jan. 2008). we consider higher isoperimetric numbers of a (finite directed) graph. In this regard we focus on the nth mean isoperimetric constant of a directed graph as the minimum of the mean outgoing normalized flows from a given set of n disjoint subsets of the vertex set of the graph. We show that the second mean isoperimetric constant in this general setting, coincides with (the mean version of) the classical Cheeger constant of the graph, while for the rest of the spectrum we show that there is a fundamental difference between the nth isoperimetric constant and the number obtained by taking the minimum over all n-partitions. In this direction, we show that our definition is the correct one in the sense that it satisfies a Federer–Fleming-type theorem, and we also define and present examples for the concept of a supergeometric graph as a graph whose mean isoperimetric constants are attained on partitions at all levels. Moreover, considering the NP-completeness of the isoperimetric problem on graphs, we address ourselves to the approximation problem where we prove general spectral inequalities that give rise to a general Cheeger-type inequality as well. On the other hand, we also consider some algorithmic aspects of the problem where we show connections to orthogonal representations of graphs and following J. Malik and J. Shi (2000) we study the close relationships to the well-known k-means algorithm and normalized cuts method. [Copyright &y& Elsevier]

Abstract: A class of simple undirected graphs is small if it contains at most labeled graphs with n vertices, for some constant α. We prove that for any constants , the class of graphs with expansion bounded by the function is small. Also, we show that the class of graphs with expansion bounded by is not small. [Copyright &y& Elsevier]

Abstract: The chromatic polynomial of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals , and . Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial . The proofs are quite simple, and employ deletion–contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27. [Copyright &y& Elsevier]

Abstract: A graph Γ is k-CS-transitive, for a positive integer k, if for any two connected isomorphic induced subgraphs A and B of Γ, each of size k, there is an automorphism of Γ taking A to B. The graph is called k-CS-homogeneous if any isomorphism between two connected induced subgraphs of size k extends to an automorphism. We consider locally-finite infinite k-CS-homogeneous and k-CS-transitive graphs. We classify those that are 3-CS-transitive (respectively homogeneous) and have more than one end. In particular, the 3-CS-homogeneous graphs with more than one end are precisely Macpherson''s locally finite distance transitive graphs. The 3-CS-transitive but non-homogeneous graphs come in two classes. The first are line graphs of semiregular trees with valencies 2 and m, while the second is a class of graphs built up from copies of the complete graph , which we describe. [Copyright &y& Elsevier]

Abstract: Let V be a set of cardinality v (possibly infinite). Two graphs G and with vertex set V are isomorphic up to complementation if is isomorphic to G or to the complement of G. Let k be a non-negative integer, G and are k-hypomorphic up to complementation if for every k-element subset K of V, the induced subgraphs and are isomorphic up to complementation. A graph G is k-reconstructible up to complementation if every graph which is k-hypomorphic to G up to complementation is in fact isomorphic to G up to complementation. We give a partial characterisation of the set of ordered pairs such that two graphs G and on the same set of n vertices are equal up to complementation whenever they are k-hypomorphic up to complementation. We prove in particular that contains all ordered pairs such that . We also prove that 4 is the least integer k such that every graph G having a large number n of vertices is k-reconstructible up to complementation; this answers a question raised by P. Ille [P. Ille, Personal communication, September 2000]. [Copyright &y& Elsevier]

Abstract: Let M denote the Laplacian matrix of a graph G. Associated with G is a finite group , obtained from the Smith normal form of M, and whose order is the number of spanning trees of G. We provide some general results on the relationship between the eigenvalues of M and the structure of , and address the question of how often the group is cyclic. [Copyright &y& Elsevier]

Abstract: A cycle decomposition of a graph Γ is a set of cycles of Γ such that every edge of Γ belongs to exactly one cycle in . Such a decomposition is called arc-transitive if the group of automorphisms of Γ that preserve setwise acts transitively on the arcs of Γ. In this paper, we study arc-transitive cycle decompositions of tetravalent graphs. In particular, we are interested in determining and enumerating arc-transitive cycle decompositions admitted by a given arc-transitive tetravalent graph. Among other results we show that a connected tetravalent arc-transitive graph is either 2-arc-transitive, or is isomorphic to the medial graph of a reflexible map, or admits exactly one cycle structure. [Copyright &y& Elsevier]

Abstract: We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible -matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to . We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion. We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs. [Copyright &y& Elsevier]

Abstract: A graph is said to be half-arc-transitive if its automorphism group acts transitively on the set of its vertices and edges but not on the set of its arcs. With each half-arc-transitive graph of valency 4 a collection of the so-called alternating cycles is associated, all of which have the same even length. Half of this length is called the radius of the graph in question. Moreover, any two adjacent alternating cycles have the same number of common vertices. If this number, the so-called attachment number, coincides with the radius, we say that the graph is tightly attached. In [D. Marušič, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B 73 (1998) 41–76], Marušič gave a classification of tightly attached half-arc-transitive graphs of valency 4 with odd radius. In this paper the even radius tightly attached graphs of valency 4 are classified, thus completing the classification of all tightly attached half-arc-transitive graphs of valency 4. [Copyright &y& Elsevier]

Abstract: A graph is k-linked if for every set of 2k distinct vertices there exist disjoint paths such that the endpoints of are and . We prove every 6-connected graph on n vertices with edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with edges that are not 3-linked for arbitrarily large values of n. [Copyright &y& Elsevier]

Abstract: Construct a graph as follows. Take a circle, and a collection of intervals from it, no three of which have union the entire circle; take a finite set of points V from the circle; and make a graph with vertex set V in which two vertices are adjacent if they both belong to one of the intervals. Such graphs are “long circular interval graphs,” and they form an important subclass of the class of all claw-free graphs. In this paper we characterize them by excluded induced subgraphs. This is a step towards the main goal of this series, to find a structural characterization of all claw-free graphs. This paper also gives an analysis of the connected claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices. [Copyright &y& Elsevier]

Abstract: A regular covering projection of connected graphs is G-admissible if G lifts along ℘. Denote by the lifted group, and let be the group of covering transformations. The projection is called G-split whenever the extension splits. In this paper, split 2-covers are considered, with a particular emphasis given to cubic symmetric graphs. Supposing that G is transitive on X, a G-split cover is said to be G-split-transitive if all complements of within are transitive on ; it is said to be G-split-sectional whenever for each complement there exists a -invariant section of ℘; and it is called G-split-mixed otherwise. It is shown, when G is an arc-transitive group, split-sectional and split-mixed 2-covers lead to canonical double covers. Split-transitive covers, however, are considerably more difficult to analyze. For cubic symmetric graphs split 2-cover are necessarily canonical double covers (that is, no G-split-transitive 2-covers exist) when G is 1-regular or 4-regular. In all other cases, that is, if G is s-regular, or 5, a necessary and sufficient condition for the existence of a transitive complement is given, and moreover, an infinite family of split-transitive 2-covers based on the alternating groups of the form is constructed. Finally, chains of consecutive 2-covers, along which an arc-transitive group G has successive lifts, are also considered. It is proved that in such a chain, at most two projections can be split. Further, it is shown that, in the context of cubic symmetric graphs, if exactly two of them are split, then one is split-transitive and the other one is either split-sectional or split-mixed. [Copyright &y& Elsevier]

Abstract: This paper considers instability of graphs in all of its possible forms. First, four theorems (one with two interesting special cases) are presented, each of which shows that graphs satisfying certain conditions are unstable. Several infinite families of graphs are investigated. For each family, the four general theorems are used to find and prove enough theorems particular for the family to explain the instability of all graphs in the family up to a certain point. A very dense family of edge-transitive unstable graphs is constructed and, at the other extreme, an unstable graph is constructed whose only symmetry is trivial. Finally, the four theorems are shown to be able to explain all instability. [Copyright &y& Elsevier]

Abstract: Let G be a d-regular graph with girth g, and let α be the independence number of G. We show that where as , and we compute explicit bounds on for small g. For large g this improves previous results for all . The method is by analysis of a simple greedy algorithm which was motivated by the differential equation method used to bound independent set sizes in random regular graphs. We use a “nibble” type of approach but require none of the sophistication of the usual nibble method arguments, relying only upon a difference equation for the expected values of certain random variables. The difference equation is approximated by a differential equation. [Copyright &y& Elsevier]

Abstract: A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of the matching decomposition procedure of Kotzig, and Lovász and Plummer. We prove a “splitter theorem” for bricks. More precisely, we show that if a brick H is a “matching minor” of a brick G, then, except for a few well-described exceptions, a graph isomorphic to H can be obtained from G by repeatedly applying a certain operation in such a way that all the intermediate graphs are bricks and have no parallel edges. The operation is as follows: first delete an edge, and for every vertex of degree two that results contract both edges incident with it. This strengthens a recent result of de Carvalho, Lucchesi and Murty. [Copyright &y& Elsevier]

Abstract: We prove a conjecture stating that the branchwidth of a graph and the branchwidth of the graph''s cycle matroid are equal if the graph has a cycle of length at least 2. [Copyright &y& Elsevier]

Abstract: We show that the problem of the existence of universal graphs with specified forbidden subgraphs can be systematically reduced to certain critical cases by a simple pruning technique which simplifies the underlying structure of the forbidden graphs, viewed as trees of blocks. As an application, we characterize the trees T for which a universal countable T-free graph exists. [Copyright &y& Elsevier]

Abstract: This is the first in the series of articles stemming from a systematical investigation of finite edge-transitive tetravalent graphs, undertaken recently by the authors. In this article, we study a special but important case in which the girth of such graphs is at most 4. In particular, we show that, except for a single arc-transitive graph on 14 vertices, every edge-transitive tetravalent graph of girth at most 4 is the skeleton of an arc-transitive map on the torus or has one of these two properties: [(1)] there exist two vertices sharing the same neighbourhood, [(2)] every edge belongs to exactly one girth cycle. Graphs with property (1) or (2) are then studied further. It is shown that they all arise either as subdivided doubles of smaller arc-transitive tetravalent graphs, or as line graphs of triangle-free -regular and -arc-transitive cubic graphs, or as partial line graphs of certain cycle decompositions of smaller tetravalent graphs. [Copyright &y& Elsevier]

Abstract: We prove that for every proper minor-closed class of graphs there exists a constant c such that for every integer n the class includes at most graphs with vertex-set . This answers a question of Welsh. [Copyright &y& Elsevier]

Abstract: A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick is minimal if for every edge e the deletion of e results in a graph that is not a brick. We prove a generation theorem for minimal bricks and two corollaries: (1) for , every minimal brick on 2n vertices has at most edges, and (2) every minimal brick has at least three vertices of degree three. [Copyright &y& Elsevier]

Abstract: We prove that every triangle-free planar graph on vertices with maximum degree three has an independent set with size at least . This was suggested and later conjectured by Albertson, Bollobás, and Tucker. [Copyright &y& Elsevier]

Abstract: We prove that every (simple) graph on vertices and at least edges either has a minor, or is isomorphic to , or is isomorphic to a graph obtained from disjoint copies of by identifying cliques of size six. The proof of one of our lemmas is computer-assisted. [Copyright &y& Elsevier]