Let G be a simple graph and G~σ be the oriented graph with G as its underlying graph and orientation σ.The rank of the adjacency matrix of G is called the rank of G and is denoted by r(G).The rank of the skew-adjace...Let G be a simple graph and G~σ be the oriented graph with G as its underlying graph and orientation σ.The rank of the adjacency matrix of G is called the rank of G and is denoted by r(G).The rank of the skew-adjacency matrix of G~σ is called the skew-rank of G~σ and is denoted by sr(G~σ).Let V(G)be the vertex set and E(G) be the edge set of G.The cyclomatic number of G,denoted by c(G),is equal to |E(G)|-|V(G)|+ω(G),where ω(G) is the number of the components of G.It is proved for any oriented graph G~σ that-2c(G)≤sr(G~σ)-r(G)≤2c(G).In this paper,we prove that there is no oriented graph G~σwith sr(G~σ)-r(G)=2c(G)-1,and in addition,there are infinitely many oriented graphs G~σ with connected underlying graphs such that c(G)=k and sr(G~σ)-r(G)=2c(G)-l for every integers k,l satisfying 0 ≤l≤4k and l≠1.展开更多
So far,the acyclic hypergraph has two different definitions.One is based on the cyclomatic number of the hypergraph,whereas the other arises from the acyclic schema of the relational database in the computer science.I...So far,the acyclic hypergraph has two different definitions.One is based on the cyclomatic number of the hypergraph,whereas the other arises from the acyclic schema of the relational database in the computer science.In this paper,it is first proved that these two definitions coincide with each other completely.Then we prove that a hypergraph H is not acyclic,or cyclic,if and only if it contains a special partial hypergraph named hypercircuit.In addition,we show that H has l(H) different hypercircuits,where l(H)is a parameter used to decide whether H is acyclic or cyclic.展开更多
The Wiener index W(G)of a graph G is a distance-based topological index defined as the sum of distances between all pairs of vertices in G.It is shown that forλ=2 there is an infinite family of planar bipartite chemi...The Wiener index W(G)of a graph G is a distance-based topological index defined as the sum of distances between all pairs of vertices in G.It is shown that forλ=2 there is an infinite family of planar bipartite chemical graphs G of girth 4 with the cyclomatic numberλ,but their line graphs are not chemical graphs,and forλ≥2 there are two infinite families of planar nonbipartite graphs G of girth 3 with the cyclomatic numberλ;the three classes of graphs have the property W(G)=W(L(G)),where L(G)is the line graph of G.展开更多
基金supported by National Natural Science Foundation of China (Nos.12171002, 12331012, 12201559)。
文摘Let G be a simple graph and G~σ be the oriented graph with G as its underlying graph and orientation σ.The rank of the adjacency matrix of G is called the rank of G and is denoted by r(G).The rank of the skew-adjacency matrix of G~σ is called the skew-rank of G~σ and is denoted by sr(G~σ).Let V(G)be the vertex set and E(G) be the edge set of G.The cyclomatic number of G,denoted by c(G),is equal to |E(G)|-|V(G)|+ω(G),where ω(G) is the number of the components of G.It is proved for any oriented graph G~σ that-2c(G)≤sr(G~σ)-r(G)≤2c(G).In this paper,we prove that there is no oriented graph G~σwith sr(G~σ)-r(G)=2c(G)-1,and in addition,there are infinitely many oriented graphs G~σ with connected underlying graphs such that c(G)=k and sr(G~σ)-r(G)=2c(G)-l for every integers k,l satisfying 0 ≤l≤4k and l≠1.
基金This research is supported by the National Natural Science Foundation of China(No. 19831080).
文摘So far,the acyclic hypergraph has two different definitions.One is based on the cyclomatic number of the hypergraph,whereas the other arises from the acyclic schema of the relational database in the computer science.In this paper,it is first proved that these two definitions coincide with each other completely.Then we prove that a hypergraph H is not acyclic,or cyclic,if and only if it contains a special partial hypergraph named hypercircuit.In addition,we show that H has l(H) different hypercircuits,where l(H)is a parameter used to decide whether H is acyclic or cyclic.
基金This work was supported by the National Natural Science Foundation of China(No.11171273)The authors would like to express their sincere gratitude to the anonymous referees for their comments and remarks,which improved the presentation of this paper.
文摘The Wiener index W(G)of a graph G is a distance-based topological index defined as the sum of distances between all pairs of vertices in G.It is shown that forλ=2 there is an infinite family of planar bipartite chemical graphs G of girth 4 with the cyclomatic numberλ,but their line graphs are not chemical graphs,and forλ≥2 there are two infinite families of planar nonbipartite graphs G of girth 3 with the cyclomatic numberλ;the three classes of graphs have the property W(G)=W(L(G)),where L(G)is the line graph of G.
