A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken ove...A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.展开更多
An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,...An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).展开更多
Because connection number can express and process synthetic uncertainties caused by various uncertainties in the transmission network planning, a connection number model (CNM) was presented to compare the values of co...Because connection number can express and process synthetic uncertainties caused by various uncertainties in the transmission network planning, a connection number model (CNM) was presented to compare the values of connection number logically. This paper proposed a novel model for transmission network flexible planning with uncertainty. In the proposed planning model both certainty and uncertainty information were included, and the cost-benefit analysis method was used to evaluate the candidate schemes in the objective function. Its good adaptability and flexibility were illustrated through two examples.展开更多
Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainb...Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc（G）, is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that trc（G） = 3 if （n-12） ＋ 1 ≤ ｜E（G）｜≤ （n2） - 1, and trc（G） ≤ 6 if ｜E（G）｜≥ （n22） ＋2. Next, we investigate the total rainbow connection numbers of graphs G with ｜V（G）｜ = n, diam（G） ≥ 2, and clique number w（G） = n - s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31（2）： 313-320] is not completely correct, and we provide a complete result for this theorem.展开更多
An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors...An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.展开更多
The connection number a+bi is a new kind of number in the Set Pair Analysis (SPA) theory. This paper applies it to network planning technique and considers the expressing, processing and controlling methods of the...The connection number a+bi is a new kind of number in the Set Pair Analysis (SPA) theory. This paper applies it to network planning technique and considers the expressing, processing and controlling methods of the synthetically uncertainties of the time limit caused by Fuzzy, random and indeterminate known factors by the connection number for a large\|scale project. The results illustrate that the new network planning and controlling method based on the connection number a+bi can provide more useful information such as primary critical paths, secondary critical paths and third critical paths etc. The new method is mroe flexible than the traditional method, and is more suitable to the practical application of project.展开更多
In 1950s, Tutte introduced the theory of nowhere-zero flows as a tool to investigate the coloring problem of maps, together with his most fascinating conjectures on nowhere-zero flows. These have been extended by Jaeg...In 1950s, Tutte introduced the theory of nowhere-zero flows as a tool to investigate the coloring problem of maps, together with his most fascinating conjectures on nowhere-zero flows. These have been extended by Jaeger et al. in 1992 to group connectivity, the nonhomogeneous form of nowhere-zero flows. Let G be a 2-edge-connected undirected graph, A be an （additive） abelian group and A＊ = A - {0}. The graph G is A-connected if G has an orientation D（G） such that for every map b ： V（G） → A satisfying ∑v∈V（G）b（v） ： 0, there is a function f ： E（G） → A＊ such that for each vertex v ∈ V（G）, the total amount of f-values on the edges directed out from v minus the total amount of f-values on the edges directed into v is equal to b（v）. The group coloring of a graph arises from the dual concept of group connectivity. There have been lots of investigations on these subjects. This survey provides a summary of researches on group connectivity and group colorings of graphs. It contains the following sections. 1. Nowhere-zero Flows and Group Connectivity of Graphs 2. Complete Families and A-reductions 3. Reductions with Edge-deletions, Vertex-deletions and Vertex-splitting 4. Group Colorings as a Dual Concept of Group Connectivity 5. Brooks Theorem, Its Variations and Dual Forms 6. Planar Graphs 7. Group Connectivity of Graphs 7.1 Highly Connected Graphs and Collapsible Graphs 7.2 Degrees Conditions 7.3 Complementary Graphs 7.4 Products of Graphs 7.5 Graphs with Diameter at Most 2 7.6 Line Graphs and Claw-Free Graphs 7.7 Triangular Graphs 7.8 Claw-decompositions and All Tutte-orientations展开更多
Each vertex of a graph G = （V, E） is said to dominate every vertex in its closed neighborhood. A set S C V is a double dominating set for G if each vertex in V is dominated by at least two vertices in S. The smalles...Each vertex of a graph G = （V, E） is said to dominate every vertex in its closed neighborhood. A set S C V is a double dominating set for G if each vertex in V is dominated by at least two vertices in S. The smallest cardinality of a double dominating set is called the double dominating number dd（G）. In this paper, new relationships between dd（G） and other domination parameters are explored and some results of [1] are extended. Furthermore, we give the Nordhaus-Gaddum-type results for double dominating number.展开更多
文摘A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.
基金supported by Hunan Education Department Foundation(No.18A382)。
文摘An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).
基金the National Natural Science Founda-tion of China (No. 50177017)the Shanghai Key Scienceand Technology Research Program (No. 041612012)
文摘Because connection number can express and process synthetic uncertainties caused by various uncertainties in the transmission network planning, a connection number model (CNM) was presented to compare the values of connection number logically. This paper proposed a novel model for transmission network flexible planning with uncertainty. In the proposed planning model both certainty and uncertainty information were included, and the cost-benefit analysis method was used to evaluate the candidate schemes in the objective function. Its good adaptability and flexibility were illustrated through two examples.
文摘Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc（G）, is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that trc（G） = 3 if （n-12） ＋ 1 ≤ ｜E（G）｜≤ （n2） - 1, and trc（G） ≤ 6 if ｜E（G）｜≥ （n22） ＋2. Next, we investigate the total rainbow connection numbers of graphs G with ｜V（G）｜ = n, diam（G） ≥ 2, and clique number w（G） = n - s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31（2）： 313-320] is not completely correct, and we provide a complete result for this theorem.
基金supported by National Natural Science Foundation of China(Grant Nos.11271267 and 11371204)
文摘An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.
文摘The connection number a+bi is a new kind of number in the Set Pair Analysis (SPA) theory. This paper applies it to network planning technique and considers the expressing, processing and controlling methods of the synthetically uncertainties of the time limit caused by Fuzzy, random and indeterminate known factors by the connection number for a large\|scale project. The results illustrate that the new network planning and controlling method based on the connection number a+bi can provide more useful information such as primary critical paths, secondary critical paths and third critical paths etc. The new method is mroe flexible than the traditional method, and is more suitable to the practical application of project.
文摘In 1950s, Tutte introduced the theory of nowhere-zero flows as a tool to investigate the coloring problem of maps, together with his most fascinating conjectures on nowhere-zero flows. These have been extended by Jaeger et al. in 1992 to group connectivity, the nonhomogeneous form of nowhere-zero flows. Let G be a 2-edge-connected undirected graph, A be an （additive） abelian group and A＊ = A - {0}. The graph G is A-connected if G has an orientation D（G） such that for every map b ： V（G） → A satisfying ∑v∈V（G）b（v） ： 0, there is a function f ： E（G） → A＊ such that for each vertex v ∈ V（G）, the total amount of f-values on the edges directed out from v minus the total amount of f-values on the edges directed into v is equal to b（v）. The group coloring of a graph arises from the dual concept of group connectivity. There have been lots of investigations on these subjects. This survey provides a summary of researches on group connectivity and group colorings of graphs. It contains the following sections. 1. Nowhere-zero Flows and Group Connectivity of Graphs 2. Complete Families and A-reductions 3. Reductions with Edge-deletions, Vertex-deletions and Vertex-splitting 4. Group Colorings as a Dual Concept of Group Connectivity 5. Brooks Theorem, Its Variations and Dual Forms 6. Planar Graphs 7. Group Connectivity of Graphs 7.1 Highly Connected Graphs and Collapsible Graphs 7.2 Degrees Conditions 7.3 Complementary Graphs 7.4 Products of Graphs 7.5 Graphs with Diameter at Most 2 7.6 Line Graphs and Claw-Free Graphs 7.7 Triangular Graphs 7.8 Claw-decompositions and All Tutte-orientations
基金the National Natural Science Foundation of China (19871036)
文摘Each vertex of a graph G = （V, E） is said to dominate every vertex in its closed neighborhood. A set S C V is a double dominating set for G if each vertex in V is dominated by at least two vertices in S. The smallest cardinality of a double dominating set is called the double dominating number dd（G）. In this paper, new relationships between dd（G） and other domination parameters are explored and some results of [1] are extended. Furthermore, we give the Nordhaus-Gaddum-type results for double dominating number.
