Das Gewicht einer Kante e = xy eines Graphen G = (V, E) ist definiert als Summe der Grade seiner Endpunkte und das Gewicht des Graphen als MInimum über alle Kantengewichte. Wir suchen für positive ganze Zahlen n,m und eine Grapheneigenschaft P den Wert: w(n,m, P) := max{w(G) : |V(G)| = n, |E(G)| = m,G in P}. Der ungarische Mathematiker Erdös formulierte 1990 auf dem Czecheslovak Symposium on Combinatorics, Graphs and Complexity die Problemstellung w(n,m, I) zu bestimmen, für die allgemeinste aller Graphenklassen I. Dieses Problem wurde zuerst teilweise von Invančo and Jendrol’ und dann endgültig von Jendrol’ and Schiermeyer gelöst. Sei G in der Graphenklasse C genau dann wenn G zusammenhängend ist. In dieser Arbeit werden Ansätze zur Bestimmung von w(n,m,C) vorgestellt. Im Speziellen betrachten wir Graphen mit bis zu 3n − 6 Kanten, sowie sehr dichte Graphen. Außerdem diskutieren wir einige verallgemeinerte Fragestellungen.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第25089号 / 理博第4996号 / 新制||理||1714(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 COLLINSBenoit Vincent Pierre, 教授 泉 正己, 准教授 山下 真由子 / 学位規則第4条第1項該当 / Doctor of Agricultural Science / Kyoto University / DFAM

The concept of \emph{proper connection number} of graphs is an extension of proper colouring and is motivated by rainbow connection number of graphs. Let $G$ be an edge-coloured graph. Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any consecutive edges receive different colours. An edge-coloured graph $G$ is called a \emph{properly connected graph} if every pair of vertices is connected by a proper path. The \emph{proper connection number}, denoted by $pc(G)$, of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ properly connected. Let $k\geq2$ be an integer. If every two vertices of an edge-coloured graph $G$ are connected by at least $k$ proper paths, then $G$ is said to be a \emph{properly $k$-connected graph}. The \emph{proper $k$-connection number} $pc_k(G)$, introduced by Borozan et al. \cite{Borozan2012}, is the smallest number of colours that are needed in order to make $G$ a properly $k$-connected graph. The aims of this dissertation are to study the proper connection number and the proper 2-connection number of several classes of connected graphs. All the main results are contained in Chapter 4, Chapter 5 and Chapter 6. Since every 2-connected graph has proper connection number at most 3 by Borozan et al. \cite{Borozan2012} and the proper connection number of a connected graph $G$ equals 1 if and only if $G$ is a complete graph by the authors in \cite{Andrews2016, Borozan2012}, our motivation is to characterize 2-connected graphs which have proper connection number 2. First of all, we disprove Conjecture 3 in \cite{Borozan2012} by constructing classes of 2-connected graphs with minimum degree $\delta(G)\geq3$ that have proper connection number 3. Furthermore, we study sufficient conditions in terms of the ratio between the minimum degree and the order of a 2-connected graph $G$ implying that $G$ has proper connection number 2. These results are presented in Chapter 4 of the dissertation. In Chapter 5, we study proper connection number at most 2 of connected graphs in the terms of connectivity and forbidden induced subgraphs $S_{i,j,k}$, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where $S_{i,j,k}$ is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common). Recently, there are not so many results on the proper $k$-connection number $pc_k(G)$, where $k\geq2$ is an integer. Hence, in Chapter 6, we consider the proper 2-connection number of several classes of connected graphs. We prove a new upper bound for $pc_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\'tal and Erd\'{o}s condition ($\alpha({G})\leq\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(G)$ and proper connection number $pc(G)$ of the Cartesian product of two nontrivial connected graphs. In the last chapter of the dissertation, we propose some open problems of the proper connection number and the proper 2-connection number.

Das Gewicht einer Kante e = xy eines Graphen G = (V, E) ist definiert als Summe der Grade seiner Endpunkte und das Gewicht des Graphen als MInimum über alle Kantengewichte. Wir suchen für positive ganze Zahlen n,m und eine Grapheneigenschaft P den Wert: w(n,m, P) := max{w(G) : |V(G)| = n, |E(G)| = m,G in P}. Der ungarische Mathematiker Erdös formulierte 1990 auf dem Czecheslovak Symposium on Combinatorics, Graphs and Complexity die Problemstellung w(n,m, I) zu bestimmen, für die allgemeinste aller Graphenklassen I. Dieses Problem wurde zuerst teilweise von Invančo and Jendrol’ und dann endgültig von Jendrol’ and Schiermeyer gelöst. Sei G in der Graphenklasse C genau dann wenn G zusammenhängend ist. In dieser Arbeit werden Ansätze zur Bestimmung von w(n,m,C) vorgestellt. Im Speziellen betrachten wir Graphen mit bis zu 3n − 6 Kanten, sowie sehr dichte Graphen. Außerdem diskutieren wir einige verallgemeinerte Fragestellungen.

In structural graph theory, connectivity is an important notation with a lot of applications. Tutte, in 1961, showed that a simple graph is 3-connected if and only if it can be generated from a wheel graph by repeatedly adding edges between nonadjacent vertices and applying vertex splitting. In 1971, Halin constructed a class of edge-minimal 3-connected planar graphs, which are a generalization of wheel graphs and later were named “Halin graphs” by Lovasz and Plummer. A Halin graph is obtained from a plane embedding of a tree with no stems having degree 2 by adding a cycle through its leaves in the natural order determined according to the embedding. Since Halin graphs were introduced, many useful properties, such as Hamiltonian, hamiltonian-connected and pancyclic, have been discovered. Hence, it will reveal many properties of a graph if we know the graph contains a spanning Halin subgraph. But unfortunately, until now, there is no positive result showing under which conditions a graph contains a spanning Halin subgraph. In this thesis, we characterize all forbidden pairs implying graphs containing spanning Halin subgraphs. Consequently, we provide a complete proof conjecture of Chen et al. Our proofs are based on Chudnovsky and Seymour’s decomposition theorem of claw-free graphs, which were published recently in a series of papers.

論文提要內容： 圖論上，定義兩點相似（similar ）：若a ，b 是圖G 上的兩點，且存在一個定義於 V （G ）的某排列φ，滿足：（１）φAut（G）及（２）φ（a）＝b，則稱G 之a，b 兩點相似。由定義吾人固然知必有一φ Aut（G），滿足φ（a）＝b，如果G 之a，b 兩點相似的話。然而，有人不禁會問：若G 上任二點a，b相似 ，則是否存在一φ Aut（G），同時滿足φ（a）＝b且φ（b）＝a呢?（ 本文稱G 為 對稱相似（symmet-rically similar），若答案為真時。） 作者在研究GRAPH RECONSTRUCTION CONJECTURE 時，亦產生相同的疑問。本文乃作者 試就此一問題，將樹形圖（Tree）加以研究，發現：凡是具有有限點的樹形圖（fin- ite tree）皆具備此特性。 本文共分二章四節。首先，吾人知：任意樹形圖乃一不具環路的聯結圖（acyclic c- onnected graph），且任二不同點a ，b 僅可決定出唯一的（a－b）路徑（ path ） 。 本文先針對此路徑觀察出二項特性：（１）當（a－b）為偶路徑，m 為其中點，且φ （a）＝b，φ Aut（G）時，φ作用在m，n之後對調（即φ（m）＝n且φ（n ）＝ m 。其證明包含在定理２．１．７及定理２．１．９之中。 其次，以定理２．１．７及定理２．１．９為基礎，本文將證明出：確實存在－φ Aut（G），同時滿足φ（a）＝b且φ（b）＝a，此處G 為一樹形圖。 由於找不到反例，本文將給一個Conjecture作為總結，即：任一有限simple圖皆具對 稱相似性。

The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.

Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB. / Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.