A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vert...A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.展开更多
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgra...Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.展开更多
Abstract. Let D （U, V, W） be an oriented 3-partite graph with ｜ U ｜ = p, ｜V｜ = q and ｜W ｜ = r. For any vertex x in D（U,V,W）, let dx^＋ and dui^- be the outdegree and indegree ofx respectively. Define aui （o...Abstract. Let D （U, V, W） be an oriented 3-partite graph with ｜ U ｜ = p, ｜V｜ = q and ｜W ｜ = r. For any vertex x in D（U,V,W）, let dx^＋ and dui^- be the outdegree and indegree ofx respectively. Define aui （or simply ai） = q ＋ r ＋ dui^＋ - dui^-, bvj （or simply b j） = p ＋ r ＋ d^＋vj - d^-vj and cwk （or simply ck） =p ＋ q ＋ dwk^＋ -dwk^- as the scores of ui in U,vj in V and wk in W respectively. The set A of distinct scores of the vertices of D（U, V, W） is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai（2 ≤ i ≤ n - 1） are even positive integers and an is any positive integer, then for n 〉 3, there exists an oriented 3-partite graph with the score set A ={a1,Σ2i=1 ai,…,Σni=1 ai}, except when A = {0, 2, 3}. Some more results for score sets in oriented 3-partite graphs are obtained.展开更多
In this paper, we study the connectedness of the invariant sets of a graph-directed iterated function system（IFS）. For a graph-directed IFS with N states, we construct N graphs. We prove that all the invariant sets ...In this paper, we study the connectedness of the invariant sets of a graph-directed iterated function system（IFS）. For a graph-directed IFS with N states, we construct N graphs. We prove that all the invariant sets are connected, if and only if all the N graphs are connected; in this case, the invariant sets are all locally connected and path connected. Our result extends the results on the connectedness of the self-similar sets.展开更多
G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to deter...G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.展开更多
A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set V(G) is called a quasi-tree graph (respectively, quas...A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set V(G) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex x ∈V(G) such that G −x?is a tree (respectively, forest). In this paper, we survey on the large numbers of maximal independent sets among all trees, forests, quasi-trees and quasi-forests. In addition, we further look into the problem of determining the third largest number of maximal independent sets among all quasi-trees and quasi-forests. Extremal graphs achieving these values are also given.展开更多
The non-wandering set Ω(f) for a graph map f is investigated. It is showed that Ω(f) is contained in the closure of the set ER(f) of eventually recurrent points of f and ω-limit set ω(Ω(f)) of Ω(f) is containe...The non-wandering set Ω(f) for a graph map f is investigated. It is showed that Ω(f) is contained in the closure of the set ER(f) of eventually recurrent points of f and ω-limit set ω(Ω(f)) of Ω(f) is contained in the closure of the set R(f) of recurrent points of f.展开更多
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.展开更多
Fault diagnosis of various systems on rolling stock has drawn the attention of many researchers. However, obtaining an optimized sensor set of these systems, which is a prerequisite for fault diagnosis, remains a majo...Fault diagnosis of various systems on rolling stock has drawn the attention of many researchers. However, obtaining an optimized sensor set of these systems, which is a prerequisite for fault diagnosis, remains a major challenge. Available literature suggests that the configuration of sensors in these systems is presently dependent on the knowledge and engineering experiences of designers, which may lead to insufficient or redundant development of various sensors. In this paper, the optimization of sensor sets is addressed by using the signed digraph （SDG） method. The method is modified for use in braking systems by the introduction of an effect-function method to replace the traditional quantitative methods. Two criteria are adopted to evaluate the capability of the sensor sets, namely, observability and resolution. The sensors configuration method of braking system is proposed. It consists of generating bipartite graphs from SDG models and then solving the set cover problem using a greedy algorithm. To demonstrate the improvement, the sensor configuration of the HP2008 braking system is investigated and fault diagnosis on a test bench is performed. The test results show that SDG algorithm can improve single-fault resolution from 6 faults to 10 faults, and with additional four brake cylinder pressure （BCP） sensors it can cover up to 67 double faults which were not considered by traditional fault diagnosis system. SDG methods are suitable for reducing redundant sensors and that the sensor sets thereby obtained are capable of detecting typical faults, such as the failure of a release valve. This study investigates the formal extension of the SDG method to the sensor configuration of braking system, as well as the adaptation supported by the effect-function method.展开更多
If G is a connected graph, the distance d (u,v) between two vertices u,v ∈ V(G) is the length of a shortest path between them. Let W = {w1, w2, ..., wk} be an ordered set of vertices of G and let v be a vertex of G ....If G is a connected graph, the distance d (u,v) between two vertices u,v ∈ V(G) is the length of a shortest path between them. Let W = {w1, w2, ..., wk} be an ordered set of vertices of G and let v be a vertex of G . The repre-sentation r(v|W) of v with respect to W is the k-tuple (d(v,w1), d(v,w2), …, d(v,wk)). . If distinct vertices of G have distinct representations with respect to W , then W is called a resolving set or locating set for G. A re-solving set of minimum cardinality is called a basis for G and this cardinality is the metric dimension of G , denoted by dim (G). A family ? of connected graphs is a family with constant metric dimension if dim (G) is finite and does not depend upon the choice of G in ?. In this paper, we show that dragon graph denoted by Tn,m and the graph obtained from prism denoted by 2Ck + {xkyk} have constant metric dimension.展开更多
LetFλ ={x∈ (0,1){2nx} ≥1/2k,n∈ z+}, z++ = {0,1,2,3,...}, k∈ N;F = U∞k=1Fλ be a decimal set in (0, 1), where {2nx} is the fractional part of a number 2nx. In this note, we prove that dirnнF = 1 and Н1(F) = 0, ...LetFλ ={x∈ (0,1){2nx} ≥1/2k,n∈ z+}, z++ = {0,1,2,3,...}, k∈ N;F = U∞k=1Fλ be a decimal set in (0, 1), where {2nx} is the fractional part of a number 2nx. In this note, we prove that dirnнF = 1 and Н1(F) = 0, where dimн is Hausdr off dimension, and Н1(F) is the Hausdorff measure of F.展开更多
We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 ...We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 , such that |N(u)∩N(v)|≥(n-2k)/4 ,then G is Hamiltonian.展开更多
This paper discusses the total irredundance relations between the graph G and its clone-contraction graph H, that is, let H be the clone-contraction graph of G and v1,v2,...,vk be all contraction vertices ofH. IfS is ...This paper discusses the total irredundance relations between the graph G and its clone-contraction graph H, that is, let H be the clone-contraction graph of G and v1,v2,...,vk be all contraction vertices ofH. IfS is a maximal total irredundant set of H such that A = S ∩ {V1,V2,…,Vk} contains as few vertices as possible, then S＇= S-A is the maximal total irredundant set of G. Furthermore, we obtain the bound of the total irredundance A（G） number： irt ≤△（G）/2△（G）＋1 n, which n is the order of graph G, and △（G） is maximum degree in G.展开更多
Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.
文摘A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.
文摘Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.
文摘Abstract. Let D （U, V, W） be an oriented 3-partite graph with ｜ U ｜ = p, ｜V｜ = q and ｜W ｜ = r. For any vertex x in D（U,V,W）, let dx^＋ and dui^- be the outdegree and indegree ofx respectively. Define aui （or simply ai） = q ＋ r ＋ dui^＋ - dui^-, bvj （or simply b j） = p ＋ r ＋ d^＋vj - d^-vj and cwk （or simply ck） =p ＋ q ＋ dwk^＋ -dwk^- as the scores of ui in U,vj in V and wk in W respectively. The set A of distinct scores of the vertices of D（U, V, W） is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai（2 ≤ i ≤ n - 1） are even positive integers and an is any positive integer, then for n 〉 3, there exists an oriented 3-partite graph with the score set A ={a1,Σ2i=1 ai,…,Σni=1 ai}, except when A = {0, 2, 3}. Some more results for score sets in oriented 3-partite graphs are obtained.
基金Supported by the Teaching Research Project of Hubei Province(2013469)the 12th Five-Year Project of Education Plan of Hubei Province(2014B379)
文摘In this paper, we study the connectedness of the invariant sets of a graph-directed iterated function system（IFS）. For a graph-directed IFS with N states, we construct N graphs. We prove that all the invariant sets are connected, if and only if all the N graphs are connected; in this case, the invariant sets are all locally connected and path connected. Our result extends the results on the connectedness of the self-similar sets.
文摘G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.
文摘A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set V(G) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex x ∈V(G) such that G −x?is a tree (respectively, forest). In this paper, we survey on the large numbers of maximal independent sets among all trees, forests, quasi-trees and quasi-forests. In addition, we further look into the problem of determining the third largest number of maximal independent sets among all quasi-trees and quasi-forests. Extremal graphs achieving these values are also given.
基金The first author is supported by the Natural Science Foundation of the Committee of Education ofJiangsu Province ( 0 2 KJB1 1 0 0 0 8)
文摘The non-wandering set Ω(f) for a graph map f is investigated. It is showed that Ω(f) is contained in the closure of the set ER(f) of eventually recurrent points of f and ω-limit set ω(Ω(f)) of Ω(f) is contained in the closure of the set R(f) of recurrent points of f.
文摘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.
基金Supported by National Hi-tech Research and Development Program of China(863 Program,Grant No.2011AA110503-3)Fundamental Research Funds for the Central Universities of China(Grant No.2860219030)Foundation of Traction Power State Key Laboratory of Southwest Jiaotong University,China(Grant No.TPL1308)
文摘Fault diagnosis of various systems on rolling stock has drawn the attention of many researchers. However, obtaining an optimized sensor set of these systems, which is a prerequisite for fault diagnosis, remains a major challenge. Available literature suggests that the configuration of sensors in these systems is presently dependent on the knowledge and engineering experiences of designers, which may lead to insufficient or redundant development of various sensors. In this paper, the optimization of sensor sets is addressed by using the signed digraph （SDG） method. The method is modified for use in braking systems by the introduction of an effect-function method to replace the traditional quantitative methods. Two criteria are adopted to evaluate the capability of the sensor sets, namely, observability and resolution. The sensors configuration method of braking system is proposed. It consists of generating bipartite graphs from SDG models and then solving the set cover problem using a greedy algorithm. To demonstrate the improvement, the sensor configuration of the HP2008 braking system is investigated and fault diagnosis on a test bench is performed. The test results show that SDG algorithm can improve single-fault resolution from 6 faults to 10 faults, and with additional four brake cylinder pressure （BCP） sensors it can cover up to 67 double faults which were not considered by traditional fault diagnosis system. SDG methods are suitable for reducing redundant sensors and that the sensor sets thereby obtained are capable of detecting typical faults, such as the failure of a release valve. This study investigates the formal extension of the SDG method to the sensor configuration of braking system, as well as the adaptation supported by the effect-function method.
文摘If G is a connected graph, the distance d (u,v) between two vertices u,v ∈ V(G) is the length of a shortest path between them. Let W = {w1, w2, ..., wk} be an ordered set of vertices of G and let v be a vertex of G . The repre-sentation r(v|W) of v with respect to W is the k-tuple (d(v,w1), d(v,w2), …, d(v,wk)). . If distinct vertices of G have distinct representations with respect to W , then W is called a resolving set or locating set for G. A re-solving set of minimum cardinality is called a basis for G and this cardinality is the metric dimension of G , denoted by dim (G). A family ? of connected graphs is a family with constant metric dimension if dim (G) is finite and does not depend upon the choice of G in ?. In this paper, we show that dragon graph denoted by Tn,m and the graph obtained from prism denoted by 2Ck + {xkyk} have constant metric dimension.
基金This work was supported by the National Natural Science Foundation of China (Grant Nos. 10041005 & 10171045).
文摘LetFλ ={x∈ (0,1){2nx} ≥1/2k,n∈ z+}, z++ = {0,1,2,3,...}, k∈ N;F = U∞k=1Fλ be a decimal set in (0, 1), where {2nx} is the fractional part of a number 2nx. In this note, we prove that dirnнF = 1 and Н1(F) = 0, where dimн is Hausdr off dimension, and Н1(F) is the Hausdorff measure of F.
文摘We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 , such that |N(u)∩N(v)|≥(n-2k)/4 ,then G is Hamiltonian.
基金Supported by the National Natural Science Foundation of China (10571071,10371048)
文摘This paper discusses the total irredundance relations between the graph G and its clone-contraction graph H, that is, let H be the clone-contraction graph of G and v1,v2,...,vk be all contraction vertices ofH. IfS is a maximal total irredundant set of H such that A = S ∩ {V1,V2,…,Vk} contains as few vertices as possible, then S＇= S-A is the maximal total irredundant set of G. Furthermore, we obtain the bound of the total irredundance A（G） number： irt ≤△（G）/2△（G）＋1 n, which n is the order of graph G, and △（G） is maximum degree in G.
文摘Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
文摘Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.
