Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are...Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.展开更多
The circular chromatic number of a graph is a natural generalization of the chromatic number. Circular chromatic number contains more information about the structure of a graph than chromatic number does. In this pape...The circular chromatic number of a graph is a natural generalization of the chromatic number. Circular chromatic number contains more information about the structure of a graph than chromatic number does. In this paper we obtain the circular chromatic numbers of special graphs such as C t k and C t k-v, and give a simple proof of the circular chromatic number of H m,n .展开更多
For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, ...For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, which have improved some best sufficient conditions published up to date.展开更多
The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which tw...The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which two vertices x and y are adjacent iff y-x∈D . This paper determines the circular chromatic numbers of two classes of distance graphs G(Z,D m,k,k+1 ) and G(Z,D m,k,k+1,k+2 ).展开更多
The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) t...The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.展开更多
The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its...The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its fractional chromatic number. This paper gives an improvement of a theorem. And we show that several classes of circulant graphs are star extremal.展开更多
The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its c...The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its circular chromatic number (also known as the star chromatic number). This paper studies the star extremality of the circulant graphs whose generating sets are of the form {±1,±k} .展开更多
For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph...For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.展开更多
Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 ...Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 = x^2 ＋ y^2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k ＋ 1 orders.展开更多
The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit desi...The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.展开更多
A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number V(G)/α(...A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number V(G)/α(G) (where V(G) is the vertex number of G and α(G) is its independence number). From this result, we get a necessary and sufficient condition for a vertex-transitive graph to be star extremal as well as a necessary and sufficient condition for a circulant graph to be star extremal. Using these conditions, we obtain several classes of star extremal graphs.展开更多
In this article we propose a new model for scheduling periodic tasks. The model is based on a variation of the circular chromatic number, called the multiple circular colouring of the conflict graph. We show that for ...In this article we propose a new model for scheduling periodic tasks. The model is based on a variation of the circular chromatic number, called the multiple circular colouring of the conflict graph. We show that for a large class of graphs, this new model will provide better solutions than the original circular chromatic number. At the same time, it allows us to avoid the difficulty of implementation when the fractional chromatic number is used.展开更多
This paper discusses a circular version of choosability of series-parallel graphs. Let χe,l denote the circular choosability （or the circular list chromatic number）. This paper proves that serial-parallel graphs of...This paper discusses a circular version of choosability of series-parallel graphs. Let χe,l denote the circular choosability （or the circular list chromatic number）. This paper proves that serial-parallel graphs of girth at least 4n ＋ 1 have circular choosability at most 2＋1/n.展开更多
An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analo...An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.展开更多
The authors give an upper bound for the projective plane crossing number of a circular graph. Also, the authors prove the projective plane crossing numbers of circular graph C （8, 3） and C （9, 3） are 2 and 1, resp...The authors give an upper bound for the projective plane crossing number of a circular graph. Also, the authors prove the projective plane crossing numbers of circular graph C （8, 3） and C （9, 3） are 2 and 1, respectively.展开更多
本文分析了圆锯片设计及制造优化中减振降噪水平与动态稳定性的研究热点与前沿理论的演进路径,基于可视化分析软件CiteSpace,以2002—2022年中国知网和Web of Science核心合集数据库为数据来源,分别从年发文量、关键词、发文作者及发文...本文分析了圆锯片设计及制造优化中减振降噪水平与动态稳定性的研究热点与前沿理论的演进路径,基于可视化分析软件CiteSpace,以2002—2022年中国知网和Web of Science核心合集数据库为数据来源,分别从年发文量、关键词、发文作者及发文机构,对圆锯片结构设计及生产工艺的一般方法及特点进行初步探讨,根据关键词时间线及突显词对未来发展趋势进行展望。研究结果表明,2002—2022年圆锯片相关研究领域的中英文文献发文量平稳,研究机构间的合作相对分散,研究热点主要集中在圆锯片结构设计优化和生产工艺优化方面。结合关键词演变知识图谱,总结了提升圆锯片减振降噪水平及动态稳定性的方法,指明了该领域未来的研究重点和发展方向。展开更多
The circular clique number of a graph G is the maximum fractional k/d suchthat G_d^k admits a homomorphism to G. In this paper, we give some sufficient conditions for graphswhose circular clique number equal the cliqu...The circular clique number of a graph G is the maximum fractional k/d suchthat G_d^k admits a homomorphism to G. In this paper, we give some sufficient conditions for graphswhose circular clique number equal the clique number, we also characterize the K_(1,3)-free graphsand planar graphs with the desired property.展开更多
基金The National Natural Science Foundation of China(No.10971025)
文摘Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.
文摘The circular chromatic number of a graph is a natural generalization of the chromatic number. Circular chromatic number contains more information about the structure of a graph than chromatic number does. In this paper we obtain the circular chromatic numbers of special graphs such as C t k and C t k-v, and give a simple proof of the circular chromatic number of H m,n .
基金Supported by National Science Foundation of China (10371048)the Science Foundation of Three Gorges University.
文摘For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, which have improved some best sufficient conditions published up to date.
文摘The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which two vertices x and y are adjacent iff y-x∈D . This paper determines the circular chromatic numbers of two classes of distance graphs G(Z,D m,k,k+1 ) and G(Z,D m,k,k+1,k+2 ).
文摘The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.
文摘The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its fractional chromatic number. This paper gives an improvement of a theorem. And we show that several classes of circulant graphs are star extremal.
文摘The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its circular chromatic number (also known as the star chromatic number). This paper studies the star extremality of the circulant graphs whose generating sets are of the form {±1,±k} .
基金The National Natural Science Foundation of China(No.10671033)
文摘For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.
文摘Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 = x^2 ＋ y^2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k ＋ 1 orders.
文摘The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.
文摘A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number V(G)/α(G) (where V(G) is the vertex number of G and α(G) is its independence number). From this result, we get a necessary and sufficient condition for a vertex-transitive graph to be star extremal as well as a necessary and sufficient condition for a circulant graph to be star extremal. Using these conditions, we obtain several classes of star extremal graphs.
文摘In this article we propose a new model for scheduling periodic tasks. The model is based on a variation of the circular chromatic number, called the multiple circular colouring of the conflict graph. We show that for a large class of graphs, this new model will provide better solutions than the original circular chromatic number. At the same time, it allows us to avoid the difficulty of implementation when the fractional chromatic number is used.
基金The National Natural Science Foundation of China (10471048),RFDP (20040422004) of Higher Education,Promotional Foundation (2005BS01016) for Middle-aged or Young Scientists of Shandong Province,and DRF of QFNU.
文摘This paper discusses a circular version of choosability of series-parallel graphs. Let χe,l denote the circular choosability （or the circular list chromatic number）. This paper proves that serial-parallel graphs of girth at least 4n ＋ 1 have circular choosability at most 2＋1/n.
基金This research is supported partially by National Natural Science Funds of China(10001035 and 10371055).
文摘An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.
基金the National Natural Science Foundation of China under Grant No.10671073Scientific Study Foundation of the Talented People Gathered by Nantong University+2 种基金Science and Technology Commission of Shanghai Municipality under Grant No.07XD14011Shanghai Leading Academic Discipline Project under Grant No.B407Natural Science Foundation of Jiangsu's Universities under Grant No.07KJB110090
文摘The authors give an upper bound for the projective plane crossing number of a circular graph. Also, the authors prove the projective plane crossing numbers of circular graph C （8, 3） and C （9, 3） are 2 and 1, respectively.
文摘本文分析了圆锯片设计及制造优化中减振降噪水平与动态稳定性的研究热点与前沿理论的演进路径,基于可视化分析软件CiteSpace,以2002—2022年中国知网和Web of Science核心合集数据库为数据来源,分别从年发文量、关键词、发文作者及发文机构,对圆锯片结构设计及生产工艺的一般方法及特点进行初步探讨,根据关键词时间线及突显词对未来发展趋势进行展望。研究结果表明,2002—2022年圆锯片相关研究领域的中英文文献发文量平稳,研究机构间的合作相对分散,研究热点主要集中在圆锯片结构设计优化和生产工艺优化方面。结合关键词演变知识图谱,总结了提升圆锯片减振降噪水平及动态稳定性的方法,指明了该领域未来的研究重点和发展方向。
基金This research is supported partially by the National Natural Science Foundation of China(10371055).
文摘The circular clique number of a graph G is the maximum fractional k/d suchthat G_d^k admits a homomorphism to G. In this paper, we give some sufficient conditions for graphswhose circular clique number equal the clique number, we also characterize the K_(1,3)-free graphsand planar graphs with the desired property.
