ICPAM - CIMPA RESEARCH SCHOOL

 

Graph labelings, graph decompositions and Hamiltonian cycles

 

International Mathematical Union (IMU)

 

 

8-19 December 2014

National University Laos, NUOL

Vientiane, Laos

 

 


 

 

About the place

Description of the Courses

Lecturers

Committees

Organization of the School

Grants

Registration and Contact

Participants

 

 

Presentation

 

The Research School covers three  topics in Graph Theory which are active fields of research and give the opportunity to present a wealth of open problems and existing  techniques to attack them.

 

Many problems in Graph Theory can be formulated in terms of labelings of graphs, or weights given to vertices and edges with prescribed algebraic or arithmetic properties. Different types of labelings, structural properties associated to them and existencial and constructive techniques will be presented in the course, together with striking open conjectures in the area. Applications of these labelings to technology and computer science will be also covered. The closely related area of Graph decompositions of graphs into parts with particular properties will also be covered in the School, including packing and covering problems, which again collect a number of well-known open conjectures. The third topic covered in the School is related to cycles and paths in graphs, particularly Hamiltonian cycles, a good example of a hard computational problem with a large number of results. Closure techniques, structural conditions and forbidden subgraph characterizations  will be covered in the course. Applications will be presented, including discussions on the Travelling Salesmen Problem.

 

The main purpose of the School is to have the participants make a start to attempt to solve some selected problems. This will be done in small groups under the guidance of the lecturers. The School will conclude with presentations of participants on their work.

 

 


---

About the Place

 

The School will take place in the Department of Mathematics at the National University of Laos.

 

 

Travel  and Local information

 

http://www.tourismlaos.org/show.php?Cont_ID=54

 

 

http://www.laosvisas.com/

 

 

Accomodation in Vientianne for foreign participants

 

Family  Hotel

Phangkham Rd, VTE, Laos PDR.

Tel : 856-21-260448 - 49

 

www.familyhotelvientiane.com

 

 

 

---

Description of the Courses

 

 

Graph Labelling began in the 1960s with graphical representations of magic squares. Over the 50 years since its genesis, the field has grown to include many labelling schemes and the resulting analyses have given rise to new aspects of graph properties, structures and classification. In this course we will consider several labelling schemes including

·       Magic-type labellings

·       Summable labellings

·       Graceful-type labellings

·       Other interesting labelling schemes if time permits.

In all cases we will investigate motivation for the scheme, construction and analysis of labellings as well as applications and implementations where appropriate.

Bibliography:

Baca., M., Miller, M., Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions, Brown Walker Press, 2008.

Marr, Alison M.; Wallis, W. D. Magic graphs. Second edition. Birkhäuser/Springer, New York, 2013.

Gallian, Joseph A.  A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998), Dynamic Survey 6, 43 pp.

 

Hamiltonian Graph Theory and Applications. This course will cover the main results in the area and discuss several of its open problems:

·       Basic concepts. Cycles and paths in graphs, Hamiltonian graphs, NP-completeness of the Hamiltonian problem.

·       Basic techniques. Degree conditions and longest cycle techniques, Toughness and the Chvátal’s conjecture, Closure techniques (based on vertex degrees (Bondy-Chvátal’s closure and k-stability, stronger closures, based on structural conditions).

·       Strong Hamiltonian properties. Pancyclicity, Hamilton connectedness, cycle extendability.

·       Relaxations of hamiltonicity. Traceability, prism-hamiltonicity, 2-factor with limited number of components, spanning k-walk, k-trestle.

·       Hamiltonicity in special classes of graphs. Squares, classes of graphs defined in terms of pairs of forbidden subgraphs, line graphs and claw-free graphs, closure and contraction techniques for claw-free graphs and line graphs.

·       Applications. Hamiltonian cycles in weighted graphs and the travelling salesman problem, approximation and heuristic algorithms, inapproximability of the problem.

·       Some open problems and conjectures.

 

Notes:

Hamiltonicity: Definitions and basic results, Evelyn Flandrin

 

Graph Decompositions. Several famous open problems in Graph Theory can be formulated in terms of decompositions of graphs into parts with particular properties. The difficulty of these problems has stimulated the creation of a great variety of techniques and a number of related problems. The course will present the main problems and known results in the area, and will provide material for the students to get themselves involved in working in several particular instances of these open problems.

·       Decomposition into equal trees: The conjectures of Ringel and Kotzig and of Graham and Haggkvist; labelings; subdivisions; recursive constructions.

·       Ascending decompositions: The conjecture of Alavi and Erdös and the tree packing conjecture.  Dense graphs, regular graphs, complete t-partite graphs. Recursive constructions, edge-coloring methods.

·       Decompositions into small number of trees: The linear arboricity conjecture. The Tuttte-NashWilliams formula. Decomposition of planar graphs, of regular graphs, of vertex transitive graphs. Connectivity and decompositions into trees.

·       Discussion of the  Alspach conjecture.

·       The double cover conjecture.

·       The Oberwolfach problem.

 

 

Bibliography:

 

Beineke, Lowell W. Graph decompositions. Surveys in graph theory (San Francisco, CA, 1995). Congr. Numer. 115 (1996), 213–226.

Chung, F. R. K.; Graham, R. L. Recent results in graph decompositions. Combinatorics (Swansea, 1981), pp. 103–123, London Math. Soc. Lecture Note Ser., 52, Cambridge Univ. Press, Cambridge-New York, 1981.

Häggkvist, Roland Decompositions of complete bipartite graphs. Surveys in combinatorics, 115–147, London Math. Soc. Lecture Note Ser., 141, Cambridge Univ. Press, Cambridge, 1989.

A.  Bonisoli Graph Decompositions and Symmetry, Surveys in Combinatorics 2009 - Cambridge University Press 365 , 1-18 (2009)

 

Notes:

Path and Cycle decompositions, Brian Alspach

 

 

Graph Enumeration. Counting is an invaluable tool in Combinatorics and Graph Theory, and one of its main tools is generating functions. The course will present the basic elements for the use of generating functions to enumerate combinatorial objects. The goal when enumerating graphs  is usually to count them up to isomorphism. This requires the introduction of the beautiful theory of Pólya. This allows the enumeration of objects  under group symmetries, which in turn requires the basics of symmetry groups acting on sets.

 

·       Revision of some counting (product rule, binomials etc).

·       Recurrence relations and applications in counting.

·       Generating functions and solving recurrence relations.

·       Revision of some introductory group theory.

·       Burnside's Theorem and Pólya counting with an emphasis on counting graphs.

 

Bibliography

 

Herbert S. Wilf. generatingfunctionology. 1994. Available at

http://www.math.upenn.edu/~wilf/DownldGF.html

 

Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. 1994. Addison-Wesley

 

 

 

---

Lecturers

 

·       Brian Alspach, University of Newcastle, Australia

·       Edy Tri Baskoro, ITB Bandung, Indonesia

·       Evelyne Flandrin, LRI, Université Paris-Sud (Orsay) and Université Paris-Descartes (Paris), France (Scientific Committee)

·       Volker Gebhardt, University of Western Sydney, Australia

·       Hao Li, University Paris-Sud, France

·       Anna Llado, UPC BarcelonaTech, Spain

·       Mirka Miller, University of Newcastle, Australia; University of West Bohemia, Pilsen, Czech Republic, King’s College, London, UK; and ITB Bandung, Indonesia (Scientific Committee)

·       Oudone Phanalasy, University of Newcastle,Australia and National University of Laos, Vientiane, Laos (Scientific Committee)

·       Joe Ryan, University of Newcastle, Australia

·       Leanne Rylands, University of Western Sydney, Australia

·       Oriol Serra, UPC BarcelonaTech, Spain (Scientific Committee)

 

---

Committees

 

Scientific Committee

 

Organizing Committee

 

Evelyne Flandrin

Mirka Miller     

Oudone Phanalasy (Chair) Oriol Serra (Chair)     

Sackmone Sirisack

 

Somchanh Bounphanmy (Chair)

Khamvane Kinnavong

Bounthan Khamphasay

Oudone Phanalasy

Sonexay Songvilay

 

 

 

CIMPA representative: Brigitte Lucquin

 

 

---

Organization of the School

 

 

Tentative program

Week 1

 

Time

Monday Dec 8

Tuesday Dec 9

Wednesday Dec 10

Thursday Dec 11

Friday Dec 12

8h-8h30

Registration

 

 

 

 

8h30-8h55

Openning

NOUL/MOES

 

 

 

 

9h-10h30

Introduction to Graph Theory

Graph labelings

Graph labelings

Graph labelings

Graph labelings

10h30-11h

Coffee Break

11h-12h30

Introduction to Graph Theory

Hamiltonian Cycles

 

Hamiltonian Cycles

 

Hamiltonian Cycles

 

Hamiltonian Cycles

 

12h30-14h

Lunch Break

14h-15h30

Graph labelings

Graph Labeling

 

Excursion

Research problem session 1

Research problem session 3

15h30-15h45

Pause

 

15h45-17h15

Hamiltonian Cycles

 

Hamiltonian Cycles

 

Research problem session 2

Research problem session 4

 

 

 

 

Week 2

 

Time

Monday Dec 15

Tuesday Dec 16

Wednesday Dec 17

Thursday Dec 18

Friday Dec 19

9h-10h30

Graph Decomposition

 

Graph Decomposition

Graph Decomposition

Graph Decomposition

Graph Decomposition

10h30-11h

Coffee Break

11h-12h30

Generating functions

 

Generating functions

 

Generating functions

 

Generating functions

 

Generating functions

 

12h30-14h

Lunch Break

14h-15h30

Research problem  Working session

 

Research problem  Working session

 

Free afternoon

Presentation session 1

Presentation session 3

15h30-15h45

Pause

 

15h45-17h15

Research problem Working session

 

Research problem Working session

 

Presentation session 2

Presentation session 4

 

Closing session

 

 

 

 

 

 

 

 

 

 

 

Topic

 

Speakers

Brief description

Introduction to Graph Theory

 

Joe Ryan

Basic terminology and basic results

Graph labelings

 

Mirka Miller, Oudone Phanalasy, Edy Tri Baskoro

Magic-type labellings, Summable labellings, Graceful-type labellings, Other interesting labelling schemes.

Hamiltonian Cycles

 

Evelyne Flandrin, Hao Li

Degree condition, toughness. Closure techniques. Pancyclicity. Hamiltnicity of special classes of graphs. Applications.

Graph Decomposition

 

Brian Alspach,  Anna Lladó

Decomposition into cycles, decompositon into trees.

Generating functions

 

Volker Gebhardt, Leanne Rylands

Generating functions, Polya theory, graph enumeration.

Open problem session

 

Brian Alspach, Volker Gebhardt, Hao Li, Mirka Miller, Oudone Phanalasy Oriol Serra

Presentation of research problems to be discussed within the course

Working session

 

Work in small groups

Work in small groups with on the presented problems

Presentation session

 

Students of the course

Presentation of conclusions on the problems discussed by the students.

 

---

Grants

 

The grant submission period is closed.

Funding by  Centre International de Mathématiques Pures et Appliquées (CIMPA),the National University of Laos (NUOL) and the International Mathematical Union (IMU)

 

     

 

 

---

Registration and contact

 

Registration will be open from September 2013.

Registration of local participants is done locally. Please contact  Oudone Phanalasy

All other participants should register through CIMPA

 

For any inquires concerning the School please contact Oudone Phanalasy

 

---

 

Participants

 

 

 

Last name

First name

Email

Address Institution

Institution Country

Akwu (Nee Akinola)

Abolape Deborah

abolaopeyemi@yahoo.co.uk

University of Ibadan

NIGERIA (NG)

Mohammadian

Ali

ali_m@ipm.ir

 Institute for Research in Fundamental Sciences (IPM),

IRAN (IR)

Ali

Kashif

akashifali@gmail.com

COMSATS INSTITUTE

PAKISTAN (PK)

Anothay

Souksomphone

 Anothay2000@yahoo.com

 Savannaket University

LAOS

Ayesha

Riasat

ayeshaa.riasat@gmail.com

University of Management & Technology

PAKISTAN (PK)

Mosbah

Mohamed

mosbah@neuf.fr

Université de Bordeaux

FRANCE (FR)

Campena

Francis Joseph

francis.campena@dlsu.edu.ph

De La Salle University

PHILIPPINES (PH)

Chanthavet

Gitar

Gitar_2015ma@yahoo.com

Champassak University

LAOS

Do

Phan Thuan

thuan.dophan@hust.edu.vn

Institut Polytechnique de Hanoi

VIET NAM (VN)

Hearty

Nuenay

hearty15200@yahoo.com.ph

MSU-Iligan Institute of Technology

PHILIPPINES (PH)

Hoan

Do Van

vanhoan310@gmail.com

Le Quy Don Technical University.

VIET NAM (VN)

Imran

Muhammad

mimran@camp.nust.edu.pk

Center for Advanced Mathematics and Physics (CAMP)

PAKISTAN (PK)

Ira Apni

Purwasih

iapurwasih@gmail.com

Institut Teknologi Bandung

INDONESIA (ID)

Jeevadoss

Shanmugasundaram

raazdoss@gmail.com

Periyar University

INDIA (IN)

Muhammad kamran

Siddiqui

kamransiddiqui75@gmail.com

Abdus Salam School of Mathematical Sciences 

PAKISTAN (PK)

Muhammad Kashif

Shafiq

kashif4v@gmail.com

GC University, Faisalabad

PAKISTAN (PK)

Phimmasone

Xayaphone

Xayaphone_p@hotmail.com

Savannaket University

LAOS

Sarfraz

Ahmad

sarfrazahmad@ciitlahore.edu.pk

COMSATS Institute of Information Technology

PAKISTAN (PK)

Saybounheaung

Thongsouk

Souk_saybounheaung@yahoo.com

 

National University of Laos

LAOS

Shabbir

Ayesha

ashinori@hotmail.com

Abdus Salam School of Mathematical Sciences

PAKISTAN (PK)

Soheila

Montaseri

soheila.montaseri@gmail.com

University of Tehran

IRAN (IR)

Songvilay

Sonexay

songvilay.sonexay@gmail.com

National University of Laos

LAOS

Suhadi Wido

Saputro

suhadinovsky@gmail.com

Institut Teknologi Bandung

INDONESIA (ID)

Syhalath

Soulagon

gons16@yahoo.com

Souphanouvong University

LAOS

Sykhotvongsa

Vilaysack

v.sykhotvongsa@yahoo.com

 

National University of Laos

LAOS

Thammavongsa

Sitar

sitarpemthammavongsa@gmail.com

 

Champassak University

LAOS

Thanavanh

Pinkham

Pin_thanavanh@yahoo.com

 

National University of Laos

LAOS

Vathanavong

Thongthiane

tthiane@gmail.com

Souphanouvong University

LAOS

Yozef Giovanni

Tjandra

yozef.g.tjandra@live.com

Institut Teknologi Bandung

INDONESIA (ID)

 

 

 

 

 

 

 

 

 

-