Abstract. Let [Formula: see text] be a 2-connected [Formula: see text]-vertex graph, and let [Formula: see text] be the total number of [Formula: see text]-cliques in [Formula: see text]. Let [Formula: see text] and [Formula: see text] be integers. In this paper, we show that if [Formula: see text] has an edge [Formula: see text] which is not on any cycle of length at least [Formula: see text], then [Formula: see text], where [Formula: see text] and [Formula: see text]. This result settles a conjecture of Ma and Yuan and provides a clique version of a result of Fan [ J. Combin. Theory Ser. B, 49 (1990), pp. 151–180], and a result of Wang and Lv [ Discrete Math., 308 (2008), pp. 113–122]. As a direct corollary, if [Formula: see text], every edge of [Formula: see text] is covered by a cycle of length at least [Formula: see text].

For a given graph $H$, a graph $G$ is H-linked if, for every injection $\varphi: V(H) \to V(G)$, the graph $G$ contains a subdivision of $H$ with $\varphi(v)$ corresponding to $v$ for each $v\in V(H)$. Let $f(H)$ be the minimum integer $k$ such that every $k$-connected graph is $H$-linked. Among connected simple graphs $H$ with at least four vertices, the exact value $f(H)$ is only known when $H$ is a star, or a path with four vertices, or a cycle with four vertices. A kite is the graph obtained from $K_4$ by deleting two adjacent edges, i.e., a triangle together with a pendant edge. The exact value of $f(H)$ when $H$ is the kite remains open. In this paper, we settle this problem by showing that every 7-connected graph is kite-linked.

Let $G$ be a graph with edge set $E(G)$ and vertex set $V(G)$, and let $T$ be a vertex subset of $G$ with even cardinality. A $T$-join of $G$ is a subset $J$ of edges such that a vertex of $G$ is incident with an odd number of edges in $J$ if and only if the vertex belongs to $T$. Minimum $T$-joins have many applications in combinatorial optimizations. In this paper, we show that a minimum $T$-join of a connected graph $G$ has at most $|E(G)|-\frac 1 2 |E(\widehat{\, G\,})|$ edges where $\widehat{\,G\,}$ is the maximum bridgeless subgraph of $G$, and the bound is optimal. Further, we are able to use this result to show that every flow-admissible signed graph $(G,\sigma)$ has a signed-circuit cover with length at most $\frac{19} 6 |E(G)|$. Particularly, a 2-edge-connected signed graph $(G,\sigma)$ with even negativeness has a signed-circuit cover with length at most $\frac 8 3 |E(G)|$.

Tutte observed that every nowhere-zero $k$-flow on a plane graph gives rise to a $k$-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph $G$ has a face-$k$-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero $k$-flow. However, if the surface is nonorientable, then a face-$k$-coloring corresponds to a nowhere-zero $k$-flow in a signed graph arising from $G$. Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive. In this paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs.

A fullerene graph F is a 3-connected plane cubic graph with exactly 12 pentagons and the remaining faces as hexagons. Let M be a perfect matching of F. A cycle C of F is M-alternating if the edges of C appear alternately in and off M. A set $\mathcal{H}$ of disjoint hexagons of F is called a resonant pattern (or sextet pattern) if F has a perfect matching M such that all hexagons in $\mathcal{H}$ are M-alternating. A fullerene graph F is k-resonant if any i ($0\leq i \leq k$) disjoint hexagons of F form a resonant pattern. In this paper, we prove that every hexagon of a fullerene graph is resonant and all leapfrog fullerene graphs are 2-resonant. Further, we show that a 3-resonant fullerene graph has at most 60 vertices and we construct all nine 3-resonant fullerene graphs, which are also k-resonant for every integer $k>3$. Finally, sextet polynomials of the 3-resonant fullerene graphs are computed.