A Graph Invariant and 2-factorizations of a graph

Details A Graph Invariant and 2-factorizations of a graph A Graph Invariant and 2-factorizations of a graph

2011-11-02

arxiv.org/abs/1111.0406v1

Mathematics

Combinatorics

8 pages,1 figure,1 Algorism

Scientific paper

A spanning subgraph of a graph G is called a [0,2]-factor of G, if for . is a union of some disjoint cycles, paths and isolate vertices, that span the graph G. It is easy to get a [0,2]-factor of G and there would be many of [0,2]-factors for a G.A characteristic number for a [0,2]-factor, which reflect the number of the paths and isolate vertices in it,is defineted. The [0,2]-factor of G is called maximum if its characteristic number is minimum, and is called characteristic number of G.It to be proved that characteristic number of graph is a graph invariant and a polynomial time algorithm for computing a maximum [0,2]-factor of a graph G has been given in this paper. A [0,2]-factor is Called a 2-factor, if its characteristic number is zero. That is, a 2-factor is a set of some disjoint cycles, that span G.We propose a A polynomial time algorism for computing 2-factor from a [0,2]-factor,which can be got easily. A HAMILTON Cycle is a 2-factor, therefore a necessary condition of a HAMILTON Graph is that, the graph have a 2-factor or the characteristic number of the graph is zero. The algorism, given in this paper, make it possible to examine the condition in polynomial time.

Affiliated with

Also associated with

No associations

Rating

A Graph Invariant and 2-factorizations of a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Graph Invariant and 2-factorizations of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Graph Invariant and 2-factorizations of a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-327641