The intersection number, in (G), has been defined as the minimumcardinality of a set S which has n different subsets S_i such that each S_i can beassigned to the node v_i of G and nodes v_i, v_j are adjacent if and on...The intersection number, in (G), has been defined as the minimumcardinality of a set S which has n different subsets S_i such that each S_i can beassigned to the node v_i of G and nodes v_i, v_j are adjacent if and onlyif S_i∩S_j ≠0. We introduce the multiset intersection number min (G), defined similarly exceptthat multisets with elements in S may now be assigned to the nodes of G. Weprove that min (G) equals the smallest number ofcliques of G whose union is G.展开更多
The hardware optimization technique of mono similarity system generation is presented based on hardware/software(HW/SW) co design.First,the coarse structure of sub graphs' matching based on full customized HW...The hardware optimization technique of mono similarity system generation is presented based on hardware/software(HW/SW) co design.First,the coarse structure of sub graphs' matching based on full customized HW/SW co design is put forward.Then,a universal sub graphs' combination method is discussed.Next,a more advanced vertexes' compression algorithm based on sub graphs' combination method is discussed with great emphasis.Experiments are done successfully with perfect results verifying all the formulas and the methods above.展开更多
Let G= (V, E) be a graph and A(G) is the collection of all minimal equitable dominating set of G. The middle equitable dominating graph of G is the graph denoted by Med(G) with vertex set the disjoint union of V∪A(G)...Let G= (V, E) be a graph and A(G) is the collection of all minimal equitable dominating set of G. The middle equitable dominating graph of G is the graph denoted by Med(G) with vertex set the disjoint union of V∪A(G) and (u, v) is an edge if and only if u ∩ v ≠ φ whenever u, v ∈ A(G) or u ∈ v whenever u ∈ v and v ∈ A(G) . In this paper, characterizations are given for graphs whose middle equitable dominating graph is connected and Kp∈Med(G) . Other properties of middle equitable dominating graphs are also obtained.展开更多
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 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.展开更多
Correlations of active and passive random intersection graphs are studied in this paper. We present the joint probability generating function for degrees of GactVe（n, re, p） and GPaSSiW（n, re, p）, which are genera...Correlations of active and passive random intersection graphs are studied in this paper. We present the joint probability generating function for degrees of GactVe（n, re, p） and GPaSSiW（n, re, p）, which are generated by a random bipartite graph G＊ （n, ~rt, p） on n ＋ rn vertices.展开更多
The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation...The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.展开更多
Let Tn be the number of triangles in the random intersection graph G(n,m,p).When the mean of Tn is bounded,we obtain an upper bound on the total variation distance between Tn and a Poisson distribution.When the mean o...Let Tn be the number of triangles in the random intersection graph G(n,m,p).When the mean of Tn is bounded,we obtain an upper bound on the total variation distance between Tn and a Poisson distribution.When the mean of Tn tends to infinity,the Stein–Tikhomirov method is used to bound the error for the normal approximation of Tn with respect to the Kolmogorov metric.展开更多
文摘The intersection number, in (G), has been defined as the minimumcardinality of a set S which has n different subsets S_i such that each S_i can beassigned to the node v_i of G and nodes v_i, v_j are adjacent if and onlyif S_i∩S_j ≠0. We introduce the multiset intersection number min (G), defined similarly exceptthat multisets with elements in S may now be assigned to the nodes of G. Weprove that min (G) equals the smallest number ofcliques of G whose union is G.
文摘The hardware optimization technique of mono similarity system generation is presented based on hardware/software(HW/SW) co design.First,the coarse structure of sub graphs' matching based on full customized HW/SW co design is put forward.Then,a universal sub graphs' combination method is discussed.Next,a more advanced vertexes' compression algorithm based on sub graphs' combination method is discussed with great emphasis.Experiments are done successfully with perfect results verifying all the formulas and the methods above.
文摘Let G= (V, E) be a graph and A(G) is the collection of all minimal equitable dominating set of G. The middle equitable dominating graph of G is the graph denoted by Med(G) with vertex set the disjoint union of V∪A(G) and (u, v) is an edge if and only if u ∩ v ≠ φ whenever u, v ∈ A(G) or u ∈ v whenever u ∈ v and v ∈ A(G) . In this paper, characterizations are given for graphs whose middle equitable dominating graph is connected and Kp∈Med(G) . Other properties of middle equitable dominating graphs are also obtained.
文摘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 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.
文摘Correlations of active and passive random intersection graphs are studied in this paper. We present the joint probability generating function for degrees of GactVe（n, re, p） and GPaSSiW（n, re, p）, which are generated by a random bipartite graph G＊ （n, ~rt, p） on n ＋ rn vertices.
基金Supported by the National Natural Science Foundation of China(31601209)the Natural Science Foundation of Hubei Province(2017CFB398)
文摘The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.
文摘Let Tn be the number of triangles in the random intersection graph G(n,m,p).When the mean of Tn is bounded,we obtain an upper bound on the total variation distance between Tn and a Poisson distribution.When the mean of Tn tends to infinity,the Stein–Tikhomirov method is used to bound the error for the normal approximation of Tn with respect to the Kolmogorov metric.
