On the size of edge-coloring critical graphs with maximum degree 4

In 1968, Vizing proposed the following conjecture: If G=(V,E) is a Δ-critical graph of order n and size m, then . This conjecture has been verified for the cases of Δ≤5. In this paper, we prove that when Δ=4. It improves the known bound for Δ=4 when n>6.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

完全r部图Kr（t）的{=C3，C2k}-强制分解（k≥4）的渐近存在性

研究基于顶点集V=Ui=1^rVi（其中｜Vi｜=t，i=1，2，……，r）的完全r部图Kr（t）的3圈和2k圈{C3，C2k}-强制分解（k≥4）的存在性问题．通过构造并运用Kr（t）的两种分解法，证明了Kr（t）的〈C3，C2k}-强制分解（k≥4）的渐近存在性，即对于任意给定的正整数k≥4，存在常数r0（k）=5k＋2，使得当r≥r0（k）时，Kr（t）的{C3，C2k}-强制分解存在的必要条件也是充分的．     

Minimally (k,k)‐edge‐connected graphs

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003     

On (Kq,k) vertex stable graphs with minimum size

A graph $G$ is a $(K_q,k)$ vertex stable graph if it contains a $K_q$ after deleting any subset of $k$ vertices. We give a characterization of $(K_q,k)$ vertex stable graphs with minimum size for $q=3,4,5$.     

On the Constant Metric Dimension of Generalized Petersen Graphs P（n, 4）

In this paper,we consider the family of generalized Petersen graphs P(n,4).We prove that the metric dimension of P(n,4) is 3 when n ≡ 0(mod 4),and is 4 when n = 4k + 3(k is even).For n ≡ 1,2(mod 4) and n = 4k + 3(k is odd),we prove that the metric dimension of P(n,4) is bounded above by 4.This shows that each graph of the family of generalized Petersen graphs P(n,4)has constant metric dimension.     

On the Zagreb indices of the line graphs of the subdivision graphs

The aim of this paper is to investigate the Zagreb indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concepts.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

Critical graphs for subpancyclicity of 3‐connected claw‐free graphs

Let be the family of graphs G such that all sufficiently large k ‐connected claw‐free graphs which contain no induced copies of G are subpancyclic. We show that for every k≥3 the family is infinite and make the first step toward the complete characterization of the family . © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 263–278, 2009     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次.图G的(s,t)-松弛强边着色指数,记作x'(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值.在图G中...     

A characterization of P4‐indifference graphs

A graph is a P₄‐indifference graph if it admits a linear ordering ≺ on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has either a ≺ b ≺ c ≺ d or d ≺ c ≺ b ≺ a. P₄‐indifference graphs generalize indifference graphs and are perfectly orderable. We give a characterization of P₄‐indifference graphs by forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 155‐162, 1999     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.