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 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 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.
文摘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.
