首页 | 本学科首页   官方微博 | 高级检索  
    检索          
共有20条相似文献,以下是第1-20项 搜索用时 312 毫秒

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 cut-vertices in which every interior region is surrounded by a regular hexagon of side length one.In the present paper we define the Z-transformation 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 cut-vertices in which every interior region is surrounded by a regular hexagon of side length one.In the present paper we define the Z-transformation 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≤m-s≤n-t,and m+n≤2s+t-1,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 m-class and t vertices in the n-class.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) =[q-g/(g-2)(p-2)], 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 f-fault q-panconnected, then for any f 〉 2, G(G0, G1; M) is (f + 1)-fault (q + 2)-panconnected.    

7.  An Iterative Rounding 2-approximation Algorithm for the k-partial Vertex Cover Problem  
   Jian-hua TU  Jun-feng DU  Feng-mei 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 k-partial vertex cover problem. There are some 2-approximation 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 k-partial 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 Vertex-disconnection 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 vertex-colored 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 vertex-disconnected 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 G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection 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 vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection 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 bi-complement 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 m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor 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 2-transformation graph (?) on the shortest-paths for G are presented heavily.    

13.  Closed 3-stop 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 k-stop-distance 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 2-stop distance is twice the standard distance between two vertices. We study the closed k-stop center and closed k-stop periphery of a graph, for k = 3.    

14.  Characterizing C6+P2-graphic Sequences  
   HU Li-li《数学季刊》,2014年第2期
   For a given graph H, a graphic sequence π = (d1, d2, ···, dn) is said to be potentially H-graphic if π has a realization containing H as a subgraph. In this paper, we characterize the potentially C6 +P2-graphic 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 lvarez-Miranda  Alfredo Candia-Vjar  Xu-jin CHEN  Xiao-dong 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 NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel 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 polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.    

16.  Bipartite graphs with the maximum sum of squares of degrees  
   Sheng-gui Zhang  Chun-cao 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 2-1 MATCHING  
   丁国力《应用数学学报(英文版)》,1987年第4期
   Given a simple bipartite graph G=(X,Y,E).M(?)E is called a 2-1 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 2-1 matching in a givenbipartite graph.We also formulate and prove a duality theorem for 2-1 matching.    

18.  K_(1,p)~k-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS  
   Du BeiliangDept.ofMath.  SuzhouUniv.  Suzhou215006.E-mail: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 ,k-factor of Km,nis aspanning subgraph F of Km,nsuch th…    

19.  D(β)-vertex-distinguishing 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(β)-vertex-distinguishing 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)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.    

20.  THE CONNECTIVITY OF Z-TRANSFORMATION GRAPHS OF PERFECT MATCHINGS OF HEXAGONAL SYSTEMS  
   张福基  郭晓峰  陈容思《应用数学学报(英文版)》,1988年第2期
   Let H be a hexagonal system.The Z-transformation 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).    

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号