Bipartite edge frustration of nut graphs: proofs and constructions
The bipartite edge frustration of a graph $G$, $\varphi(G)$, is the minimum number of edges that must be removed from $G$ to obtain a graph that is bipartite. Core graphs are singular graphs on $2$ or more vertices, for which the kernel of the adjacency matrix contains a full eigenvector. A nut graph is a core graph of nullity one. Nut graphs $G$ are non-bipartite. It is proved here that $\varphi(G) \geq 2$ if $G$ is a nut graph, i.e. every nut graph requires deletion of at least two edges to produce a bipartite graph. In addition, we give a constructive proof that for every integer $k \geq…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.15679
curl -X POST /api/v1/records/arxiv/2610.15679/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.15679/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'