摘要
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.
基金
supported by National Natural Science Foundation of China (Nos.12171002, 12331012, 12201559)。
