Contractible edges in some k-connected graphs

An edge e of a k-connected graph G is said to be k-contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k-connected. In 2002, Kawarabayashi proved that for any odd integer k ? 5, if G is a k-connected graph and G contains no subgraph D = K ₁ + (K ₂ ∪ K _1,2), then G has a k-contractible edge. In this paper, by generalizing this result, we prove that for any integer t ? 3 and any odd integer k ? 2t + 1, if a k-connected graph G contains neither K ₁ + (K ₂ ∪ K _1,t ), nor K ₁ + (2K ₂ ∪ K _1,2), then G has a k-contractible edge.     

Minimal non-1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph K₇-K₃ is the unique 7-vertex MN-graph.     

Removable edges of cycles in 5-connected graphs

Let G be a 5-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G?e; second, for each vertex x of degree 4 in G?e, delete x from G?e and then completely connect the 4 neighbors of x by K ₄. If multiple edges occur, we use single edge to replace them. The final resultant graph is denoted by G ? e. If G ? e is still 5-connected, then e is called a removable edge of G. In this paper, we investigate the distribution of removable edges in a cycle of a 5-connected graph. And we give examples to show some of our results are best possible in some sense.     

Chromaticity of certain tripartite graphs identified with a path

For a graph G, let P(G) be its chromatic polynomial. Two graphs G and H are chromatically equivalent if P(G)=P(H). A graph G is chromatically unique if P(H)=P(G) implies that H≅G. In this paper, we classify the chromatic classes of graphs obtained from K_2,2,2∪P_m(m?3), (K_2,2,2-e)∪P_m(m?5) and (K_2,2,2-2e)∪P_m(m?6) by identifying the end-vertices of the path P_m with any two vertices of K_2,2,2, K_2,2,2-e and K_2,2,2-2e, respectively, where e and 2e are, respectively, an edge and any two edges of K_2,2,2. As a by-product of this, we obtain some families of chromatically unique and chromatically equivalent classes of graphs.     

Minimal 2-matching-covered graphs

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G−e is not 2-matching-covered for all edges e of G. We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K₂ and K₄ is 2 and to prove that a minimal 2-matching-covered graph other than K₄ cannot contain a complete subgraph with at least 4 vertices.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

Infinite families of crossing-critical graphs with a given crossing number

A graph is crossing-critical if deleting any edge decreases its crossing number on the plane. It is proved that, for any n ? 3, there is an infinite family of 3-connected crossing-critical graphs with crossing number n.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

A bound on the total size of a cut cover

A cycle cover (cut cover) of a graph G is a collection of cycles (cuts) of G that covers every edge of G at least once. The total size of a cycle cover (cut cover) is the sum of the number of edges of the cycles (cuts) in the cover.We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K₄ or K₈). This corresponds to the result of Fan [J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1.     

一类连通无三角形图线图的共色数的下界

Erd(o)s,Gimbel and Straight (1990) conjectured that if ω(G)＜5 and z(G)＞3,then z(G)≥χ(G)-2. But by using the concept of edge cochromatic number it is proved that if G is the line graph of a connected triangle-free graph with ω(G)＜5 and G≠K4, then z(G)≥χ(G)-2.     

On vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.     

A characterization of block graphs

A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let N_e(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈N_e(u) and y∈N_e(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22].     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

Clique graphs of time graphs

A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that v_iv_j ∈ e(G) for v_i ≠ v_j if and only if |f(v_i) ? f(v_j)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K²(G), and inductively, denote K(K^m?1(G)) by K^m(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kⁿ(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived.     

Minimally 3-restricted edge connected graphs

For a connected graph G=(V,E), an edge set S⊂E is a 3-restricted edge cut if G−S is disconnected and every component of G−S has order at least three. The cardinality of a minimum 3-restricted edge cut of G is the 3-restricted edge connectivity of G, denoted by λ₃(G). A graph G is called minimally 3-restricted edge connected if λ₃(G−e)<λ₃(G) for each edge e∈E. A graph G is λ₃-optimal if λ₃(G)=ξ₃(G), where , ω(U) is the number of edges between U and V?U, and G[U] is the subgraph of G induced by vertex set U. We show in this paper that a minimally 3-restricted edge connected graph is always λ₃-optimal except the 3-cube.     

On a valence problem in extremal graph theory

Let L ≠ Kinp be a p-chromatic graph and e be an edge of L such that L ? e is (p?1)-chromatic If Gⁿ is a graph of n vertices without containing L but containing K_p, then the minimum valence of Gⁿ is

$\text{?n}\text{1?}\text{1}\text{p?}\text{3}\text{2}\text{+}\text{O}\text{(1).}$

     

Edge degrees and dominating cycles

The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e₁)+d(e₂)>|V(G)|-4 for any remote edges e₁,e₂, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ₂(G)>|V(G)|/2, then all longest cycles are dominating.     

On the structure of k-connected graphs without Kk-minor

Suppose G is a k-connected graph that does not contain K_k as a minor. What does G look like? This question is motivated by Hadwiger’s conjecture (Vierteljahrsschr. Naturforsch. Ges. Zürich 88 (1943) 133) and a deep result of Robertson and Seymour (J. Combin. Theory Ser. B. 89 (2003) 43).It is easy to see that such a graph cannot contain a (k−1)-clique, but could contain a (k−2)-clique, as K_k−5+G′, where G′ is a 5-connected planar graph, shows. In this paper, however, we will prove that such a graph cannot contain three “nearly” disjoint (k−2)-cliques. This theorem generalizes some early results by Robertson et al. (Combinatorica 13 (1993) 279) and Kawarabayashi and Toft (Combinatorica (in press)).     

On the maximum number of diagonals of a circuit in a graph

For a graph G, let ?(G) denote the maximum number k such that G contains a circuit with k diagonals.Theorem. For any graph G with minimum valency$\text{n? 3, ?(G) ?}\text{1}\text{2}\text{(n+1)(n-2)}$.If the equality holds and G is connected, then either G is isomorphic to K_n+1 or G is separable and each of its terminal blocks is isomorphic to K_n+1, or K_n+1 with one edge subdivided.     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.