The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, whe...The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, where d( u ) denotes the degree of a vertex u in G. The paper mainly provides the upper and lower bounds of the exponential Randić index in quasi-tree graphs, and characterizes the extremal graphs when the bounds are achieved.展开更多
A connected graph G = （V, E） is called a quasi-tree graph, if there exists a vertex vo ∈ V（G） such that G - v0 is a tree. Liu and Lu [Linear Algebra Appl. 428 （2008） 2708- 2714] determined the maximal spectral ...A connected graph G = （V, E） is called a quasi-tree graph, if there exists a vertex vo ∈ V（G） such that G - v0 is a tree. Liu and Lu [Linear Algebra Appl. 428 （2008） 2708- 2714] determined the maximal spectral radius together with the corresponding graph among all quasi-tree graphs on n vertices. In this paper, we extend their result, and determine the second to the fifth largest spectral radii together with the corresponding graphs among all quasi-tree graphs on n vertices.展开更多
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.展开更多
This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking （GTCFC） for space-borne commercial-off-the-shelf （COTS） processo...This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking （GTCFC） for space-borne commercial-off-the-shelf （COTS） processors. A graph tree data structure with a topology similar to common trees is introduced to transform the control flow graphs of target programs. This together with design of IDs and signatures of its vertices and edges allows for an easy check of legality of actual branching during target program execution. As a result, the algorithm not only is capable of detecting all single and multiple branching errors with low latency and time overheads along with a linear-complexity space overhead, but also remains generic among arbitrary instruction sets and independent of any specific hardware. Tests of the algorithm using a COTS-processor-based onboard computer （OBC） of in-service ZDPS-1A pico-satellite products show that GTCFC can detect over 90% of the randomly injected and all-pattern-covering branching errors for different types of target programs, with performance and overheads consistent with the theoretical analysis; and beats well-established preeminent control flow checking algorithms in these dimensions. Furthermore, it is validated that GTCGC not only can be accommodated in pico-satellites conveniently with still sufficient system margins left, but also has the ability to minimize the risk of control flow errors being undetected in their space missions. Therefore, due to its effectiveness, efficiency, and compatibility, the GTCFC solution is ready for applications on COTS processors on pico-satellites in their real space missions.展开更多
A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which i...A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.展开更多
A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and numb...A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.展开更多
In this paper a new modeling framework for the dependability analysis of complex systems is presented and related to dynamic fault trees (DFTs). The methodology is based on a modular approach: two separate models are ...In this paper a new modeling framework for the dependability analysis of complex systems is presented and related to dynamic fault trees (DFTs). The methodology is based on a modular approach: two separate models are used to handle, the fault logic and the stochastic dependencies of the system. Thus, the fault schema, free of any dependency logic, can be easily evaluated, while the dependency schema allows the modeler to design new kind of non-trivial dependencies not easily caught by the traditional holistic methodologies. Moreover, the use of a dependency schema allows building a pure behavioral model that can be used for various kinds of dependability studies. In the paper is shown how to build and integrate the two modular models and convert them in a Stochastic Activity Network. Furthermore, based on the construction of the schema that embeds the stochastic dependencies, the procedure to convert DFTs into static fault trees is shown, allowing the resolution of DFTs in a very efficient way.展开更多
Let T(G)be the tree graph of a simple graph G.It is proved that ifT and T′are two vertices of T(G)such that d_T(G)(T)(?)d_T(G}(T′),then there ared_T(G)(T) internally disjoint paths in T(G) joining T and T′.
In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tr...In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tree colorable are given. Moreover, a series of uniquely tree colorable graphs are constructed.展开更多
The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that ther...The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.展开更多
Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of ...Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.展开更多
Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design...Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.展开更多
A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G conta...A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G contains a spanning 3-ended tree, where σk（G） = min{∑es deg（v） ： S is an independent set of G with ｜S｜ = k}.展开更多
文摘The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, where d( u ) denotes the degree of a vertex u in G. The paper mainly provides the upper and lower bounds of the exponential Randić index in quasi-tree graphs, and characterizes the extremal graphs when the bounds are achieved.
基金Supported by the National Natural Science Foundation of China(Grant No.11171290)the Natural Science Foundation of Jiangsu Province(Grant No.BK20151295)
文摘A connected graph G = （V, E） is called a quasi-tree graph, if there exists a vertex vo ∈ V（G） such that G - v0 is a tree. Liu and Lu [Linear Algebra Appl. 428 （2008） 2708- 2714] determined the maximal spectral radius together with the corresponding graph among all quasi-tree graphs on n vertices. In this paper, we extend their result, and determine the second to the fifth largest spectral radii together with the corresponding graphs among all quasi-tree graphs on n vertices.
文摘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.
基金supported by National Natural Science Foundation of China (No. 60904090)
文摘This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking （GTCFC） for space-borne commercial-off-the-shelf （COTS） processors. A graph tree data structure with a topology similar to common trees is introduced to transform the control flow graphs of target programs. This together with design of IDs and signatures of its vertices and edges allows for an easy check of legality of actual branching during target program execution. As a result, the algorithm not only is capable of detecting all single and multiple branching errors with low latency and time overheads along with a linear-complexity space overhead, but also remains generic among arbitrary instruction sets and independent of any specific hardware. Tests of the algorithm using a COTS-processor-based onboard computer （OBC） of in-service ZDPS-1A pico-satellite products show that GTCFC can detect over 90% of the randomly injected and all-pattern-covering branching errors for different types of target programs, with performance and overheads consistent with the theoretical analysis; and beats well-established preeminent control flow checking algorithms in these dimensions. Furthermore, it is validated that GTCGC not only can be accommodated in pico-satellites conveniently with still sufficient system margins left, but also has the ability to minimize the risk of control flow errors being undetected in their space missions. Therefore, due to its effectiveness, efficiency, and compatibility, the GTCFC solution is ready for applications on COTS processors on pico-satellites in their real space missions.
文摘A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.
文摘A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.
文摘In this paper a new modeling framework for the dependability analysis of complex systems is presented and related to dynamic fault trees (DFTs). The methodology is based on a modular approach: two separate models are used to handle, the fault logic and the stochastic dependencies of the system. Thus, the fault schema, free of any dependency logic, can be easily evaluated, while the dependency schema allows the modeler to design new kind of non-trivial dependencies not easily caught by the traditional holistic methodologies. Moreover, the use of a dependency schema allows building a pure behavioral model that can be used for various kinds of dependability studies. In the paper is shown how to build and integrate the two modular models and convert them in a Stochastic Activity Network. Furthermore, based on the construction of the schema that embeds the stochastic dependencies, the procedure to convert DFTs into static fault trees is shown, allowing the resolution of DFTs in a very efficient way.
文摘Let T(G)be the tree graph of a simple graph G.It is proved that ifT and T′are two vertices of T(G)such that d_T(G)(T)(?)d_T(G}(T′),then there ared_T(G)(T) internally disjoint paths in T(G) joining T and T′.
文摘In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tree colorable are given. Moreover, a series of uniquely tree colorable graphs are constructed.
文摘The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.
基金Project supported by the National Natural Science Foundation of China （Grant No.10571117）, and the Development Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）
文摘Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.
文摘Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.
基金Supported by the National Natural Science Foundation of China,Tian Yuan Special Foundation(Grant No.11426125)by Educational Commission of Liaoning Province(Grant No.L2014239)
文摘A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G contains a spanning 3-ended tree, where σk（G） = min{∑es deg（v） ： S is an independent set of G with ｜S｜ = k}.
