Font Size: a A A

Nowhere-zero 3-flow In The Cubic Of Graphs

Posted on:2008-11-02Degree:MasterType:Thesis
Country:ChinaCandidate:C G YuFull Text:PDF
GTID:2120360215455860Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
In the paper, we prove that G~2 admits 3 - NZF if and only if G (?) A, moreover, we prove that G~k (k≥3) admits 3 - NZF if and only if H (?) A″in which H is any branch of G.The paper is divided into three parts: the first one, we give the commonly notations and terminologies, some previous conclusions and conjectures about the flows, on the base of which according to general research techniques of Graph Theory, as well as the conceptions of the Square of Graphs and the Cube of Graphs, which will be used in the proof in the theorem that G~2 admits 3-NZF and G~k(k≥3) admits 3 - NZF, it's innovation way lies in for any higher order graph, it may be decomposed to a graph whose vertexes or edges are less, then viewing the composition graph G as the backing, thus we consider the proposition that G satisfies if and only if G~k (k≥2) admits 3 - NZF. The second part, we mainly give the proposition that the edge deleting graph G of G~2 satisfies if and only if G~2 admits 3 - NZF, that is, G~2 admits 3-NZF if and only if G(?)A, moreover on the base of k = 2, it gives the corollary that G~k (k≥3) admits 3-NZF. The last part, we mainly give the proof that G~k(k≥3) admits 3 - NZF, that is, G~k(k≥3) admits 3-NZF if and only if H(?)A″in which H is any branch of G.
Keywords/Search Tags:the Square of Graphs, the Cube of Graphs, 3 - NZF, Modk - flow
PDF Full Text Request
Related items