The cycle space of a graph G is the set of all spanning Eulerian subgraphs of G, i.e. spanning subgraphs in which all vertices have even degrees. This is a vector space over the finite field of two elements with the operation of symmetric difference of the edge sets. We observe that this space is closed under isomorphism, i.e. if a subgraph H of G belongs to it, then any subgraph of G isomorphic to H also belongs to this space. Obviously, the same is true for the space of all spanning subgraphs of G. How many vector spaces closed under isomorphism can a graph have? It is known that if G is the complete graph \(K_n\) , then it has at most 14 vector spaces closed under isomorphism regardless of the value of n. In the present paper, we reveal the relationships between these spaces and prove that all of them can be obtained from the above two by means of four operations. We also reveal some relationships between vector spaces of a complete bipartite graph closed under isomorphism.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Vector Spaces of Graphs Closed Under Isomorphism

  • Vadim Lozin,
  • D. V. Zakharova

摘要

The cycle space of a graph G is the set of all spanning Eulerian subgraphs of G, i.e. spanning subgraphs in which all vertices have even degrees. This is a vector space over the finite field of two elements with the operation of symmetric difference of the edge sets. We observe that this space is closed under isomorphism, i.e. if a subgraph H of G belongs to it, then any subgraph of G isomorphic to H also belongs to this space. Obviously, the same is true for the space of all spanning subgraphs of G. How many vector spaces closed under isomorphism can a graph have? It is known that if G is the complete graph \(K_n\) , then it has at most 14 vector spaces closed under isomorphism regardless of the value of n. In the present paper, we reveal the relationships between these spaces and prove that all of them can be obtained from the above two by means of four operations. We also reveal some relationships between vector spaces of a complete bipartite graph closed under isomorphism.