Abstract:
We study the Optimal Linear Arrangement (OLA) problem of Halin graphs, one of the simplest classes of non-outerplanar graphs. We present several properties of OLA of general Halin graphs. We prove a lower bound on the cost of OLA of any Halin graph, and define classes of Halin graphs for which the cost of OLA matches this lower bound. We show for these classes of Halin graphs, OLA can be computed in O(n log n), where n is the number of vertices.

Abstract:
The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large graphs.

Abstract:
Let $T$ be a tree with no degree 2 vertices and $L(T)=\{l_1,\ldots,l_r\}, r \geq 2$ denote the set of leaves in $T$. An Halin graph $G$ is a graph obtained from $T$ such that $V(G)=V(T)$ and $E(G)=E(T) \cup \{\{l_i,l_{i+1}\} ~|~ 1 \leq i \leq r-1\} \cup \{l_1,l_r\}$. In this paper, we investigate combinatorial problems such as, testing whether a given graph is Halin or not, chromatic bounds, an algorithm to color Halin graphs with the minimum number of colors. Further, we present polynomial-time algorithms for testing and coloring problems.

Abstract:
The quadratic traveling salesman problem (QTSP) is to find a least cost Hamiltonian cycle in an edge-weighted graph. We define a restricted version of QTSP, the $k$-neighbour TSP (TSP($k$)), and give a linear time algorithm to solve TSP($k$) on a Halin graph for $k\leq 3$. This algorithm can be extended to solve TSP($k$) on any fully reducible class of graphs for any fixed $k$ in polynomial time. This result generalizes corresponding results for the standard TSP. Further, these results are useful in establishing approximation bounds based on domination analysis. TSP($k$) can be used to model various machine scheduling problems including an optimal routing problem for UAVs.

Abstract:
For a connected labelled graph $G$, a {\em spanning tree} $T$ is a connected and an acyclic subgraph that spans all the vertices of $G$. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of $G$. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of $O((2pd)^{p})$ processors for parallel algorithmics, where $d$ and $p$ are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is $O((2pd)^{p})$.

Abstract:
A k-dimensional box is the Cartesian product R_1 x R_2 x ... x R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K_4, then box(G)=2. In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then box(G)=2 unless G is isomorphic to K_4 (in which case its boxicity is 1).

Abstract:
We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with $k$ colours, there is a trivial greedy algorithm that finds a maximal matching in $k-1$ synchronous communication rounds. The present work shows that the greedy algorithm is optimal in the general case: any algorithm that finds a maximal matching in anonymous, $k$-edge-coloured graphs requires $k-1$ rounds. If we focus on graphs of maximum degree $\Delta$, it is known that a maximal matching can be found in $O(\Delta + \log^* k)$ rounds, and prior work implies a lower bound of $\Omega(\polylog(\Delta) + \log^* k)$ rounds. Our work closes the gap between upper and lower bounds: the complexity is $\Theta(\Delta + \log^* k)$ rounds. To our knowledge, this is the first linear-in-$\Delta$ lower bound for the distributed complexity of a classical graph problem.

Abstract:
We show that there exist linear-time algorithms that compute the strong chromatic index of Halin graphs, of maximal outerplanar graphs and of distance-hereditary graphs.

Abstract:
A spanning tree with no vertices of degree 2 is called a Homeomorphically irreducible spanning tree\,(HIST). Based on a HIST embedded in the plane, a Halin graph is formed by connecting the leaves of the tree into a cycle following the cyclic order determined by the embedding. Both of the determination problems of whether a graph contains a HIST or whether a graph contains a spanning Halin graph are shown to be NP-complete. It was conjectured by Albertson, Berman, Hutchinson, and Thomassen in 1990 that a {\it every surface triangulation of at least four vertices contains a HIST}\,(confirmed). And it was conjectured by Lov\'asz and Plummer that {\it every 4-connected plane triangulation contains a spanning Halin graph}\,(disproved). Balancing the above two facts, in this paper, we consider generalized Halin graphs, a family of graph structures which are "stronger" than HISTs but "weaker" than Halin graphs in the sense of their construction constraints. To be exact, a generalized Halin graph is formed from a HIST by connecting its leaves into a cycle. Since a generalized Halin graph needs not to be planar, we investigate the minimum degree condition for a graph to contain it as a spanning subgraph. We show that there exists a positive integer $n_0$ such that any 3-connected graph with $n\ge n_0$ vertices and minimum degree at least $(2n+3)/5$ contains a spanning generalized Halin graph. As an application, the result implies that under the same condition, the graph $G$ contains a wheel-minor of order at least $n/2$. The minimum degree condition in the result is best possible.