1.

Graphs isomorphic to their maximum matching graphs





Yan Liu Gui Ying Yan《数学学报(英文版)》,2009年第25卷第9期


The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.

2.

Z—Transformation Graphs of perfect Matchings of Hexagonal Systems





张福基 郭晓峰 陈荣斯《新疆大学学报(理工版)》,1987年第1期


A hexagonal system is defined to be a finit connected plane graph with no cutvertices in which every interior region is surrounded by a regular hexagon of side length one.In the present paper we define the Ztransformation graph of a hexagonal system H to be the graph where vertices are the perfect matchings of (?) and where two perfect matchings are joint by an edge provided their symmetric difference is a hexagon of H.We prove that,if H has perfect matchings,Z(H)is a connected bipartite graph.Besides,Z(H)is either an elementary chain or a graph with girth 4.Some further results are obtained also.

3.

Z—Transformation Graphs of perfect Matchings of Hexagonal Systems





张福基 郭晓峰 陈荣斯《新疆大学学报(理工版)》,1987年第1期


A hexagonal system is defined to be a finit connected plane graph with no cutvertices in which every interior region is surrounded by a regular hexagon of side length one.In the present paper we define the Ztransformation graph of a hexagonal system H to be the graph where vertices are the perfect matchings of (?) and where two perfect matchings are joint by an edge provided their symmetric difference is a hexagon of H.We prove that,if H has perfect matchings,Z(H)is a connected bipartite graph.Besides,Z(H)is either an elementary chain or a graph with girth 4.Some further results are obtained also.

4.

本刊英文版Vol.27(2011),No.11论文摘要





《数学学报》,2012年第1期


<正>For a bipartite graph G on m and n vertices,respectively,in its vertices classes, and for integers s and t such that 2≤s≤t,0≤ms≤nt,and m+n≤2s+t1,we prove that if G has at least mn (2(m  s) + n  t) edges then it contains a subdivision of the complete bipartite K_((s,t)) with s vertices in the mclass and t vertices in the nclass.Furthermore, we characterize the corresponding extremal bipartite graphs with mn (2(m  s) + n  t + 1) edges for this topological Turan type problem.

5.

Properties of πskew Graphs with Applications





《数学学报(英文版)》,2021年第4期


The skewness of a graph G, denoted by sk(G), is the minimum number of edges in G whose removal results in a planar graph.It is an important parameter that measures how close a graph is to planarity, and it is complementary, and computationally equivalent, to the Maximum Planar Subgraph Problem.For any connected graph G on p vertices and q edges with girth g, one can easily verify that sk(G) ≥π(G), where π(G) =[qg/(g2)(p2)], and the graph G is said to be πskew if equality holds.The concept of πskew was first proposed by G.L.Chia and C.L.Lee.The πskew graphs with girth 3 are precisely the graphs that contain a triangulation as a spanning subgraph.The purpose of this paper is to explore the properties of πskew graphs.Some families of πskew graphs are obtained by applying these properties, including join of two graphs, complete multipartite graphs and Cartesian product of two graphs.We also discuss the threshold for the existence of a spanning triangulation.Among other results some sufficient conditions regarding the regularity and size of a graph, which ensure a spanning triangulation, are given.

6.

Panconnectivity for interconnection networks with faulty elements





Mei Lu Hui Qing Liu《数学学报(英文版)》,2010年第26卷第4期


Let Go and G1 be two graphs with the same vertices. The new graph G（G0, G1; M） is a graph with the vertex set V（0o） ∪）V（G1） and the edge set E（Go） UE（G1） UM, where M is an arbitrary perfect matching between the vertices of Go and G1, i.e., a set of cross edges with one endvertex in Go and the other endvertex in G1. In this paper, we will show that if Go and G1 are ffault qpanconnected, then for any f 〉 2, G（G0, G1; M） is （f ＋ 1）fault （q ＋ 2）panconnected.

7.

An Iterative Rounding 2approximation Algorithm for the kpartial Vertex Cover Problem





Jianhua TU Junfeng DU Fengmei YANG《应用数学学报(英文版)》,2014年第30卷第2期


We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the kpartial vertex cover problem. There are some 2approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）approximation for the kpartial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.

8.

The Rainbow Vertexdisconnection in Graphs





Xu Qing BAI You CHEN Ping LI Xue Liang LI Yin Di WENG《数学学报(英文版)》,2021年第37卷第2期


Let G be a nontrivial connected and vertexcolored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertexdisconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of GS; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(Gxy)S. For a connected graph G, the rainbow vertexdisconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertexdisconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertexdisconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.

9.

Pancyclism and Bipancyclism of Hamiltonian Graphs





张社民《数学研究与评论》,1988年第2期


A graph G on n vertices is called pancyclic if it contains cycles of everylength k, for 3≤k≤n. A bipartite graph on 2n vertices is called bipancyclicif it contains cycles of every even length 2k, for 2≤k≤n. In this paper,we consider only finite, undirected graphs without loops ormultipie edges. We shall give a new sufficient condition ensuring a Hamiltonian graph tobe pancyclic(or bipancyclic), The main results are the following two theorems.Theorem A. Let G be a Hamiltonian graph of order n. If there exisis a

10.

Matching Polynomials of Special Graphs





《新疆大学学报(理工版)》,1989年第1期


Farrell in [1] and Godsil and Gutman in [2] gave different definitions about matching polynomials ?? this paper we use the definition of [1] If G is a graph,m(G,i) will denote the number of matchings in G,i.e.,the number of selections of i independent edges of G.If i=0,We define m(G,0)=1.If G has n vertices,we call the polyrnomial ??? to be the matching polynomial of G.By ? we denote the complement of G obtained by deleting the edges of G from the complete graph ? denote the bipartite graph with bipartition m and n By ? we denote the bicomplement of ? obtained by deleting the edges of ?from ? (where ? is the complete bipartite graph with bipartition m and n).

11.

<Emphasis Type="Italic">k</Emphasis>factors in regular graphs





Wai Chee Shiu Gui Zhen Liu《数学学报(英文版)》,2008年第24卷第7期


Plesnik in 1972 proved that an （m  1）edge connected mregular graph of even order has a 1factor containing any given edge and has another 1factor excluding any given m  1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）edgeconnected bipartite graph, then G has a 1factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edgeconnectivity for an nregular graph to have a kfactor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.

12.

网络最短的最优解集结构





张振坤 王斌《数学季刊》,2007年第22卷第4期


The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2transformation graph (?) on the shortestpaths for G are presented heavily.

13.

Closed 3stop center and periphery in graphs





Linda Eroh Ralucca Gera Steven J. Winters《数学学报(英文版)》,2012年第28卷第3期


A delivery person must leave the central location of the business, deliver packages at a number of addresses, and then return. Naturally, he/she wishes to reduce costs by finding the most efficient route. This motivates the following: Given a set of k distinct vertices S = { x1, x2, . . . , xk } in a simple graph G, the closed kstopdistance of set S is defined to be dk( S) = min θ∈P (S ) (d(θ(x1), θ(x2)) + d(θ(x2), θ(x3)) + ··· + d(θ(xk), θ(x1))), where P (S) is the set of all permutations of S. That is the same as saying that dk( S) is the length of a shortest closed walk through the vertices { x1, . . . , xk }. The closed 2stop distance is twice the standard distance between two vertices. We study the closed kstop center and closed kstop periphery of a graph, for k = 3.

14.

Characterizing C6＋P2graphic Sequences





HU Lili《数学季刊》,2014年第2期


For a given graph H, a graphic sequence π = （d1, d2, ···, dn） is said to be potentially Hgraphic if π has a realization containing H as a subgraph. In this paper, we characterize the potentially C6 ＋P2graphic sequences where C6 ＋P2 denotes the graph obtained from C6 by adding two adjacent edges to the three pairwise nonadjacent vertices of C6. Moreover, we use the characterization to determine the value ofσ（C6＋P2, n）.

15.

Risk models for the Prize Collecting Steiner Tree problems with interval data





Eduardo lvarezMiranda Alfredo CandiaVjar Xujin CHEN Xiaodong HU Bi LI《应用数学学报(英文版)》,2014年第30卷第1期


Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NPhard in general,it is polynomialtime solvable when graphs G are restricted to seriesparallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c+e]while taking risk(c+e xe)/(c+e c e)of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p+v]for its inclusion in T while taking risk(yv p v)/(p+v p v)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomialtime algorithms solving these problems on seriesparallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NPhard problems even if the original optimization problems are polynomialtime solvable.

16.

Bipartite graphs with the maximum sum of squares of degrees





Shenggui Zhang Chuncao Zhou《应用数学学报(英文版)》,2014年第30卷第3期


In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.

17.

ON THE MAXIMUM 21 MATCHING





丁国力《应用数学学报(英文版)》,1987年第4期


Given a simple bipartite graph G=(X,Y,E).M(?)E is called a 21 matching of G if:1)(?)x∈X,either two edges or none in M is incident to x and 2)(?)y∈Y,at most one edge in M is incident to y.In this paper,we describe an efficient algorithm for finding a maximum 21 matching in a givenbipartite graph.We also formulate and prove a duality theorem for 21 matching.

18.

K_(1,p)~kFACTORIZATION OF COMPLETE BIPARTITE GRAPHS





Du BeiliangDept.ofMath. SuzhouUniv. Suzhou215006.Email:dubl@pub.sz.jsinfo.ne《高校应用数学学报(英文版)》,2001年第2期


§ 1 IntroductionLet Km,nbe a complete bipartite graph with two vertex sets having m and n vertices,respectively.A subgraph F of Km,n is called a spanning subgraph of Km,nif F contains allthe vertices of Km,n.Itis clearthata graph with no isolated vertices is uniquely determinedby the setofits edges.So in this paper,we considera graph with no isolated vertices to bea setof2 elementsets ofits vertices.Letk be a positive integer.A K1 ,kfactor of Km,nis aspanning subgraph F of Km,nsuch th…

19.

D(β)vertexdistinguishing total coloring of graphs 被引次数：2





ZHANG Zhongfu LI Jingwen CHEN Xiang'en YAO Bing WANG Wenjie & QIU Pengxiang Institute of Applied Mathematic Lanzhou Jiaotong University Lanzhou 730070 China College of Mathematics and Information Science Northwest Normal University Lanzhou 730070 China College of Information and Electrical Engineering Lanzhou Jiaotong University Lanzhou 730070 China《中国科学A辑(英文版)》,2006年第10期


A new concept of the D(β)vertexdistinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger thanβhave different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)vertexdistinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.

20.

THE CONNECTIVITY OF ZTRANSFORMATION GRAPHS OF PERFECT MATCHINGS OF HEXAGONAL SYSTEMS





张福基 郭晓峰 陈容思《应用数学学报(英文版)》,1988年第2期


Let H be a hexagonal system.The Ztransformation graph Z(H) is a graph where the vertices are perfect matchings of H and where two perfect matchings are joined by an edge provided their symmetric difference consists of six edges of a hexagon of H. We prove that the connectivity of Z(H) is equal to the minimum degree of vertices of Z(H).
