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.     

Connected,locally 2-connected,K1,3-free graphs are panconnected

A graph G is locally n-connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n-connected. We prove that every connected, locally 2-connected graph containing no induced subgraph isomorphic to K_1,3 is panconnected.     

A note on locally connected and hamiltonian-connected graphs

A graphG is locallyn-connected,n≧1, if the subgraph induced by the neighborhood of each vertex isn-connected. It is shown that every connected, locally 3-connected graph containing no induced subgraph isomorphic toK(1, 3) is hamiltonian-connected.     

Removable edges in 3-connected graphs

An edge e of a 3-connected graph G is said to be removable if G - e is a subdivision of a 3-connected graph. If e is not removable, then e is said to be nonremovable. In this paper, we study the distribution of removable edges in 3-connected graphs and prove that a 3-connected graph of order n ≥ 5 has at most [(4 n — 5)/3] nonremovable edges.     

A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs

In 1956, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows.     

Vertices of Degree 5 in a Contraction Critically 5-connected Graph

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.     

Contractible Triples in Highly Connected Graphs

We prove that if G is k-connected (with k ≥ 2), then G contains either a cycle of length 4 or a connected subgraph of order 3 whose contraction results in a k-connected graph. This immediately implies that any k-connected graph has either a cycle of length 4 or a connected subgraph of order 3 whose deletion results in a (k − 1)-connected graph.     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

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.     

Two-Connected Augmentation Problems in Planar Graphs

Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting subgraph satisfies specified (edge or vertex) connectivity requirements between pairs of nodes of S. This has important applications in upgrading telecommunication networks to be invulnerable to link or node failures. We give a polynomial algorithm for this problem when S is connected, nodes are required to be at most 2-connected, and G is planar. Applications to network design and multicommodity cut problems are also discussed.     

F-Planar graphs

An F-planar graph, where F is an ordered field, is a graph that can be represented in the plane F × F, with non-crossing line segments as edges. It is shown that the graph G is F-planar for some F if and only if every finite subgraph of G is planar.     

局部连通图的群Z_3-连通性

本文研究了局部连通图的群连通性的问题.利用不断收缩非平凡Z_3-连通子图的方法,在G是3-边连通且局部连通的无爪无沙漏图的情况下,获得了G不是群Z_3-连通的当且仅当G是K_4或W_5.推广了当G是2-边连通且局部3-边连通时,G是群Z_3-连通的这个结果.     

The contractible subgraph of 5-connected graphs

An edge e of a k-connected graph G is said to be k-removable if G — e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction results still in a k-connected graph. A k-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k-connected. In this paper, we show that there is a contractible subgraph in a 5-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally 5-connected graph is contained in some triangle.     

On (<Emphasis Type="Italic">p</Emphasis>, 1)-total labelling of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.     

On the Structure of Contractible Edges in <Emphasis Type="Italic">k</Emphasis>-connected Partial <Emphasis Type="Italic">k</Emphasis>-trees

Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least |V(G)| + k − 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees.     

The number of contractible edges in 3-connected graphs

An edge of a 3-connected graph is calledcontractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has |G|/2 or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphsG have more than |G|/2 contractible edges.     

The structure of 1-planar graphs

A graph is called 1-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge. In the paper, we study the existence of subgraphs of bounded degrees in 1-planar graphs. It is shown that each 1-planar graph contains a vertex of degree at most 7; we also prove that each 3-connected 1-planar graph contains an edge with both endvertices of degrees at most 20, and we present similar results concerning bigger structures in 1-planar graphs with additional constraints.     

A characterization of Hamiltonian prisms

A characterization is established for a graph G to have a Hamilton cycle in G × K₂, the prism over G. Moreover, it is shown that every 3-connected graph has a 2-connected spanning bipartite subgraph. Using this result, the existence of a Hamilton cycle in the prism over every 3-connected cubic graph is established. Further, the existence of a Hamilton cycle in the prism over a cubic 2-connected graph is also discussed. Earlier results in this direction are shown to be particular cases of the results obtained here. © 1993 John Wiley & Sons, Inc.     

A property of weighted graphs without induced cycles of nonpositive weights

It has been conjectured [B. Xu, On signed cycle domination in graphs, Discrete Math. 309 (4) (2009) 1007–1012] that if there is a mapping from the edge set of a 2-connected graph G to {−1,1} such that for each induced subgraph, that is a cycle, the sum of all numbers assigned to its edges by this mapping is positive, then the number of all those edges of G to which 1 is assigned, is more than the number of all other edges of G. This conjecture follows from the main result of this note: If a mapping assigns integers as weights to the edges of a 2-connected graphGsuch that for each edge, its weight is not more than 1 and for each cycle which is an induced subgraph ofG, the sum of all weights of its edges is positive, then the sum of all weights of the edges ofGalso is positive. A simple corollary of this result is the following: If?is a mapping from the edge set of a 2-connected graphGto a set of real numbers such that for each cycleCofG, ∑_e∈E(C)?(e)>0, then∑_e∈E(G)?(e)also is positive.     

Connectivity of intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper, we classify finite solvable groups whose intersection graphs are not 2-connected and finite nilpotent groups whose intersection graphs are not 3-connected. Our methods are elementary.