Reconstruction of distance hereditary 2-connected graphs

A graph is reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabelled subgraphs. It is shown that all distance hereditary 2-connected graphs $G$ such that $\text{diam}\left(G\right)=2$ or $\text{diam}\left(G\right)=\text{diam}\left(\overline{G}\right)=3$ are reconstructible.     

Large cycles in 4-connected graphs

The first result states that every 4-connected graph G with minimum degree δ and connectivity κ either contains a cycle of length at least 4δ−κ−4 or every longest cycle in G is a dominating cycle. The second result states that any such graph under the additional condition δ≥α either contains a cycle of length at least 4δ−κ−4 or is hamiltonian, where α denotes the independence number of G. Both results are sharp in all respects.     

The extremal function for 3-linked graphs

A graph is k-linked if for every set of 2k distinct vertices {s₁,…,s_k,t₁,…,t_k} there exist disjoint paths P₁,…,P_k such that the endpoints of P_i are s_i and t_i. We prove every 6-connected graph on n vertices with 5n−14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with 5n−15 edges that are not 3-linked for arbitrarily large values of n.     

Generating thec *5-connected graphs

A planar 3-valent 3-connected graph is said to becyclically n-connected provided it is possible to separate two circuits by cutting edges, and at leastn edges must be cut to do so. The graph is said to bestrongly cyclically n-connected provided it is cyclicallyn-connected and any separation of two circuits by cutting edges leaves one component consisting of just a simple circuit. We give a method of generating all strongly cyclically 5-connected graphs by certain types of facet splitting.     

On the minor-minimal 2-connected graphs having a fixed minor

Let H be a graph with κ₁ components and κ₂ blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ₁−1)+β(κ₂−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.     

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.     

Some properties of contraction-critical 5-connected graphs

Let k be a positive integer and let G be a k-connected graph. An edge of G is called k-contractible if its contraction still results in a k-connected graph. A non-complete k-connected graph G is called contraction-critical if G has no k-contractible edge. Let G be a contraction-critical 5-connected graph, Su proved in [J. Su, Vertices of degree 5 in contraction-critical 5-connected graphs, J. Guangxi Normal Univ. 17 (3) (1997) 12-16 (in Chinese)] that each vertex of G is adjacent to at least two vertices of degree 5, and thus G has at least vertices of degree 5. In this paper, we further study the properties of contraction-critical 5-connected graph. In the process, we investigate the structure of the subgraph induced by the vertices of degree 5 of G. As a result, we prove that a contraction-critical 5-connected graph G has at least vertices of degree 5.     

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.     

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 distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On an upper bound of the spectral radius of graphs

We give some upper bounds for the spectral radius of bipartite graph and graph, which improve the result in Hong’s Paper [Y. Hong, J.-L. Shu, K. Fang, A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B 81 (2001) 177-183].     

Pairs of Hamiltonian circuits in 5-connected planar graphs

Settling a problem raised by B. Grünbaum, J. Malkevitch, and the author, we present 5-valent 5-connected planar graphs that admit no pairs of edgedisjoint Hamiltonian circuits; our smallest example has 176 vertices. This is used to construct an infinite family of 5-valent 5-connected planar graphs, in which every member has the property that any pair of Hamiltonian circuits in it share at least about $\text{1}\text{168}$ of their edges. We construct 4- and 5-valent, 3-connected non-Hamiltonian planar graphs.     

Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.     

On -connected graphs

A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs.     

Local structure of 5- and 6-connected graphs

We prove that if graph on n vertices is minimally and contraction critically 5-connected, then it has 4n/7 vertices of degree 5. We also prove that if graph on n vertices is minimally and contraction critically 6-connected, then it has n/2 vertices of degree 6. Bibliography: 7 titles.     

Some structural properties of minimally contraction-critically 5-connected graphs

An edge of a k-connected graph is said to be k-removable (resp. k-contractible) if the removal (resp. the contraction ) of the edge results in a k-connected graph. A k-connected graph with neither k-removable edge nor k-contractible edge is said to be minimally contraction-critically k-connected. We show that around an edge whose both end vertices have degree greater than 5 of a minimally contraction-critically 5-connected graph, there exists one of two specified configurations. Using this fact, we prove that each minimally contraction-critically 5-connected graph on n vertices has at least vertices of degree 5.