TITLE

# Small Components of the 5-Subgraph of a Contraction-critically 5-Connected Graph

AUTHOR(S)
Ando, Kiyoshi
PUB. DATE
November 2017
SOURCE
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1485
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
The subgraph of a 5-connected graph G induced by the set of degree 5 vertices is said to be the 5-subgraph of G. An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. We show that there are exact two graphs with order 5 which can be a component of the 5-subgraph of a contraction-critically 5-connected graph.
ACCESSION #
126308056

## Related Articles

• On 3-Regular Bipancyclic Subgraphs of Hypercubes. Borse, Y. M.; Shaikh, S. R. // International Journal of Combinatorics;5/5/2015, Vol. 2015, p1

The n-dimensional hypercube Qn is bipancyclic; that is, it contains a cycle of every even length from 4 to 2n. In this paper, we prove that Qnâ€‰â€‰(nâ‰¥3) contains a 3-regular, 3-connected, bipancyclic subgraph with l vertices for every even l from 8 to 2n except 10.

• Further Properties of Trees with Minimal Atom-Bond Connectivity Index. Jianping Liu; Jinsong Chen // Abstract & Applied Analysis;2014, p1

Let G = (V, E) be a graph the atom-bond connectivity (ABC) index is defined as the sum of weights ((du + dv - 2 ) /dudv)1/2 over all edges uv of G, where du denotes the degree of a vertex u of G. In this paper, we determined a few structural features of the trees with minimal ABC index also we...

• Independent Monopoly Size In Graphs. Naji, Ahmed Mohammed; Soner, N. D. // Applications & Applied Mathematics;Dec2015, Vol. 10 Issue 2, p738

In a graph G = (V;E), a set D âŠ† V (G) is said to be a monopoly set of G if every vertex v 2 V âˆŠD has at least d(v)/2 neighbors in D. The monopoly size of G, denoted mo(G), is the minimum cardinality of a monopoly set among all monopoly sets in G. The set D âŠ† V (G) is an...

• A NEIGHBORHOOD UNION CONDITION FOR FRACTIONAL (k; n';m)-CRITICAL DELETED GRAPHS. YUN GAO; FARAHANI, MOHAMMAD REZA; WEI GAO // Transactions on Combinatorics;2017, Vol. 6 Issue 1, p13

A graph G is called a fractional (k; n ' ;m)-critical deleted graph if any n ' vertices are removed from G the resulting graph is a fractional (k;m)-deleted graph. In this paper, we prove that for integers for each pair of non-adjacent vertices x, y of G, then G is a fractional (k; n '...

• THE CONDITION FOR A SEQUENCE TO BE POTENTIALLY AL,M- GRAPHIC. PIRZADA, SHARIEFUDDIN; CHAT, BILAL A. // Transactions on Combinatorics;2017, Vol. 6 Issue 1, p21

The set of all non-increasing non-negative integer sequences Ï€ = (d1, d2,...,dn) is denoted by NSn. A sequence Ï€ Îµ NSn is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of Ï€. The set of all graphic...

• Cycle Lengths of Hamiltonian $$P_\ell$$ -free Graphs. Meierling, Dirk; Rautenbach, Dieter // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2335

For an integer $$\ell$$ at least three, we prove that every Hamiltonian $$P_\ell$$ -free graph $$G$$ on $$n>\ell$$ vertices has cycles of at least $$\frac{2}{\ell }n-1$$ different lengths. For small values of $$\ell$$ , we can improve the bound as follows. If $$4\le \ell \le 7$$ , then $$G$$...

• Signed Roman $$k$$ -Domination in Graphs. Henning, Michael; Volkmann, Lutz // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p175

Let $$k\ge 1$$ be an integer, and let $$G$$ be a finite and simple graph with vertex set $$V(G)$$ . A signed Roman $$k$$ -dominating function (SRkDF) on a graph $$G$$ is a function $$f:V(G)\rightarrow \{-1,1,2\}$$ satisfying the conditions that (i) $$\sum _{x\in N[v]}f(x)\ge k$$ for each vertex...

• On Evenly-Equitable, Balanced Edge-Colorings and Related Notions. Erzurumluoğlu, Aras; Rodger, C. A. // International Journal of Combinatorics;3/4/2015, Vol. 2015, p1

A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color iâˆˆZk={0,1,â€¦,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an...

• A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs. Wideł, Wojciech // Discussiones Mathematicae: Graph Theory;Feb2016, Vol. 36 Issue 1, p173

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v âˆˆ V ( K), dK( u, v) = 2 implies . In this...

• Invariants Concerning f -Domination in Graphs. SANMING ZHOU // Bulletin of the Malaysian Mathematical Sciences Society;2014, Vol. 37 Issue 4, p1047

Given a graph G and a function f : V(G) â†’ {0,1,2, ...}, a subset D of V(G) is called an f -dominating set of G if every vertex x outside D is adjacent to at least f (x) vertices in D. In this article we study a few graphical invariants relating to this concept.

Share