User:Qadir Hosseini1360/sandbox: Difference between revisions
No edit summary |
No edit summary |
||
Line 62: | Line 62: | ||
================================================================================================================================================== |
================================================================================================================================================== |
||
'''Cycle decomposition of K_n |
'''Cycle decomposition of <math>K_n</math> & <math>K_n-I</math> .'''<ref> http://www.sciencedirect.com/science/article/pii/S0095895600919968</ref> |
||
Brian Alspach and Heather Gavlas have established necessary and sufficient conditions for decomposition of the [[complete graph]] of even order minus a 1-factor into even cycles and the complete graph of odd order into odd cycle. |
Brian Alspach and Heather Gavlas have established necessary and sufficient conditions for decomposition of the [[complete graph]] of even order minus a 1-factor into even cycles and the complete graph of odd order into odd cycle. |
Revision as of 23:52, 31 March 2014
Initial draft
- Fix the math by putting in
- Figure out how to break the page into biography page and cycle decomposition page.
Brian Alspach
Brian Alspach is one of the most influential graph theorists of the past four decades. His works and fundamental discoveries have had significant impact on several mainstream subjects of graph theory.
Biography
Brian Alspach was born on May 29, 1938 in North Dakota. He has one brother and one sister. At the age of nine his family moved to Seattle Washington. He attended the University of Washington from 1957 to 1961. Receiving his B.A. from the university of Washington in 1961. He did not immediately pursue his master’s degree. After receiving his B.A. degree he thought at a junior high school for one year. He married in 1961 to a woman named Linda. After separating he married another mathematician named Kathy Heinrich in 1980. From his first marriage Brian had two children and four grandchildren. In 1962 he went back to school to pursue his graduate degree. He received his graduate degree and his PHD at the University of California at Santa Barbara. In 1964 he received his masters degree and in 1966 he obtained his PHD. He thought at Simon Fraser University for 33 years. He retires from there in 1998. He currently works as an adjunct professor at Regina and has been there since 1999. He is responsible for creating an industrial mathematics degree at Simon Fraser University. [1]
Brian Alspach believes that the growth and future of mathematics will be dependent on business people in the industrial business. His interests are in graph theory and its application. One of his theories of coverings and decomposition has been applied to scheduling issues that can arise in the business world. Mr.Alspach states that his biggest issue with this is trying to explain such complex math to people in the business world with a basic understanding of math. Brian Alspach has dedicated his life to mentoring and supporting young mathematicians. While residing in Vancouver with his wife Kathy, Brian was known for holding BBQ’s for students pursuing their degrees and careers in mathematics. His signature dish was a barbequed wild salmon with a side of spinach salad. Brian has an interest in Jazz music. He also has been taking piano lessons on his free time since his retirement. He loves to travel with his wife. Their house is full of the art work they have purchased on their travels. Brian has mentored a total of 13 Ph.D. students all of which have been able to successfully defend their thesis. Mr. Alspach has vowed not to take on anymore Ph.D. students. His wife is the vice president of academics at the University of Regina where he is currently an adjunct professor. With his free time Brian has found a keen interest in the math involved in poker. He writes articles regularly for Poker Digest and Canadian Poker Player magazine. [2]
======================================================================================================================================
Mathematical contributions
1) Brian Alspach & Heather Gavlas “Cycle decomposition of & K_n-I”.
Journal of Combinatorial Theory, Series B, 81.1 (Jan 2001): pag 77-99 [3]
2) Brain alspach “Isomorphism of circulant graphs and digraphs”.
Discrecte Mathematics, 25.2 (Feb 1979): pag . 97-108 [4]
3) Brian Alspach & T.D.Parsons “A construction for vertex –transitive graph “
Canadian Journal of Mathematics, 35.2 (Apr 1982): page. 257-297 [5]
4) Brain Alspach & Dragan Marusic and lewis Nowitz “ Constructing graph which are ½ -transitive “
Journal of the Australian Mathematical Society, Series A, 56.03 (June 1994) pag 391-402 [6]
5) Brain Alspach “The Oberwolfach problem and factors of uniform odd length cycles”
Journal of Combinatorial Theory, Series A, 52.1 (Sep 1989) pag 20-43 [7]
6) Brain Alspach “Cycles of each length in regular tournaments”
Canadian Mathematical Bulletin, 10.2 (Nov 1967) pag 173-331 [8]
7) Brian Alspach “Point-symmetric graphs and digraphs of prime order and transitive permutation groups of prime degree”
Journal of Combinatorial Theory, Series B, 15.1 (Aug 1973): pag 12-17 [9]
8) Brain Alspach “The classification of hamiltonian generalized Petersen graphs”
Journal of Combinatorial Theory, Series B, 34.3 (Jun 1983) pag 293-312 [10]
======================================================================================================================================
Cycle decomposition of & .[11]
Brian Alspach and Heather Gavlas have established necessary and sufficient conditions for decomposition of the complete graph of even order minus a 1-factor into even cycles and the complete graph of odd order into odd cycle.
DEFINITIONS AND PRELIMINARIES
1) Decomposition of a graph: Given a graph G we can dissect this graph to proper subgraphs the way that no two subgraph would have the same edge and the union of these subgraph will give us the original graph. we can call these subgraphs the Decomposition of G. For Example in graph G the set of subgraphs H_1,…,H_k that partition of the edges of G. That is, for all i and j H_i+⋯+H_k=G and E(H_i )∩E(H_j )=∅
2) Cycle decomposition: A cycle decomposition is a decomposition such that each subgraph H_i in the decomposition is a cycle. Every vertex in a graph that has cycle decomposition must have even degree.
3) Spanning Subgraph: H is a spanning subgraph of G, if H is obtains by only edge dilation of graph G. Therefore Graph H has all the vertices of graph G.
4) r-factor of a graph: A spanning subgraph H of graph G is called a r-factor of G if H is a regular if degree r. Therefore all vertices of H shall have the same degree to be called r-factor.
5) 1-factor of a graph: A spanning subgraph H of graph G is called a 1-factor of G if H is a regular if degree r. Therefore all vertices of H shall have the same degree to be called 1-factor.
=============================================================================================================================================================
In order for any graph to be decomposable into cycles, the degrees of the vertices of the graph must be even. Therefore the complete graph must have an odd number of vertices or a complete graph with an even number of vertices after removing a 1-factore from it.
The complete graph of n vertices is denoted by K_n , and K_n-I denotes the complete graph of n vertices with a 1-factor I removed.
Theorem 1.1: For positive even integers m and n with 4≤m≤n , the graph K_n-I can be decomposed into cycles of length m if and only if the number of edges in K_n-I is a multiple of m.
Theorem1.2: For positive odd integers m and n with 3≤m≤n , the graph K_n can be decomposed into cycles of length m if and only if the number of edges in K_n is a multiple of m.
References
The bounds on the value of n in terms of m:
1st : For m and n odd , it is sufficient to consider value of m and n with m≤n≤3m.
2nd : For m and n even , it is sufficient to consider value of m and n with m≤n≤2m.
- ^ www.mathcentral.uregina.ca/humanface/career/profiles/brianalspach.pdf
- ^ www.sciencedirect.com/science/article/pii/S001236X5002815
- ^ http://www.sciencedirect.com/science/article/pii/S0095895600919968
- ^ http://www.sciencedirect.com/science/article/pii/0012365X79900116
- ^ http://books.google.com/books?hl=en&lr=&id=mLY6nc-D10sC&oi=fnd&pg=PA307&dq=brian+alspach&ots=6jT4HRptmE&sig=Vyk08EvRa8E3Imm0WIAX2h3lkLc#v=onepage&q=brian%20alspach&f=false
- ^ http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=4935324
- ^ http://www.sciencedirect.com/science/article/pii/0097316589900599
- ^ http://www.sciencedirect.com/science/article/pii/0097316589900599
- ^ http://www.sciencedirect.com/science/article/pii/0095895673900270
- ^ http://www.sciencedirect.com/science/article/pii/0095895683900424
- ^ http://www.sciencedirect.com/science/article/pii/S0095895600919968