Back to search

West Virginia University

Flows on Signed Graphs

Abstract

dc:description.abstract

This dissertation focuses on integer flow problems within specific signed graphs. The theory of integer flows, which serves as a dual problem to vertex coloring of planar graphs, was initially introduced by Tutte as a tool related to the Four-Color Theorem. This theory has been extended to signed graphs. In 1983, Bouchet proposed a conjecture asserting that every flow-admissible signed graph admits a nowhere-zero 6-flow. To narrow dawn the focus, we investigate cubic signed graphs in Chapter 2. We prove that every flow-admissible 3-edge-colorable cubic signed graph admits a nowhere-zero 10-flow. This together with the 4-color theorem implies that every flow-admissible bridgeless planar signed graph admits a nowhere-zero 10-flow. As a byproduct of this research, we also demonstrate that every flow-admissible hamiltonian signed graph can admit a nowhere-zero 8-flow. In Chapter 3, we delve into triangularly connected signed graphs. Here, A triangle-path in a graph G is defined as a sequence of distinct triangles T1,T2,\ldots,Tm in G such that for any i, j with $1\leq i < j \leq m$, |E(Ti)\cap E(Ti+1)|=1 and E(Ti)\cap E(Tj)=\emptyset if $j > i+1$. We categorize a connected graph $G$ as triangularly connected if it can be demonstrated that for any two nonparallel edges $e$ and $e'$, there exists a triangle-path T1T2\cdots Tm such that e\in E(T1) and e'\in E(Tm). For ordinary graphs, Fan {\it et al.} characterized all triangularly connected graphs that admit nowhere-zero $3$-flows or $4$-flows. Corollaries of this result extended to integer flow in certain families of ordinary graphs, such as locally connected graphs due to Lai and certain types of products of graphs due to Imrich et al. In this dissertation, we extend Fan's result for triangularly connected graphs to signed graphs. We proved that a flow-admissible triangularly connected signed graph (G,σ) admits a nowhere-zero $4$-flow if and only if (G,σ) is not the wheel W5 associated with a specific signature. Moreover, this result is proven to be sharp since we identify infinitely many unbalanced triangularly connected signed graphs that can admit a nowhere-zero 4-flow but not 3-flow.\\ Chapter 4 investigates integer flow problems within K4-minor free signed graphs. A minor of a graph $G$ refers to any graph that can be derived from $G$ through a series of vertex and edge deletions and edge contractions. A graph is considered K4-minor free if K4 is not a minor of $G$. While Bouchet's conjecture is known to be tight for some signed graphs with a flow number of 6. Kompi\v{s}ov\'{a} and M\'{a}\v{c}ajov\'{a} extended those signed graph with a specific signature to a family $\M$, and they also put forward a conjecture that suggests if a flow-admissible signed graph does not admit a nowhere-zero 5-flow, then it belongs to $\M$. In this dissertation, we delve into the members in $\M$ that are K4-minor free, designating this subfamily as $\N$. We provide a proof demonstrating that every flow-admissible, K4-minor free signed graph admits a nowhere-zero 5-flow if and only if it does not belong to the specified family $\N$.

Degree

thesis:*
Name thesis:degree_name
PhD
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematics

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Chong
Contributors dc:contributor
  • Rong Luo
  • John Goldwasser
  • Hong-Jian Lai
  • Dong Ye
  • Cun-Quan Zhang

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Identifier
<p><a href="https://orcid.org/0009-0000-7242-5444">https://orcid.org/0009-0000-7242-5444</a></p>
https://researchrepository.wvu.edu/etd/12171

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Li, Chong. Flows on Signed Graphs. Dissertation thesis, https://doi.org/10.33915/etd.12171