Boxicity of series-parallel graphs

We show that there exist series-parallel graphs with boxicity 3.     

Boxicity of line graphs

The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Q_d, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).     

Minimum cycle bases of Halin graphs

Halin graphs are planar 3‐connected graphs that consist of a tree and a cycle connecting the end vertices of the tree. It is shown that all Halin graphs that are not “necklaces” have a unique minimum cycle basis. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 150–155, 2003     

Multiobjective traveling salesperson problem on Halin graphs

In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.     

Halin图中的Hamilton路径

本文证明了所有的Ｈａｌｉｎ图都是Ｈａｍｉｌｔｏｎ连通的，并给出反例，说明Ｈａｌｉｎ图中存在两条独立边不包含在任何Ｈａｍｉｌｔｏｎ圈中。     

Antimagic orientation of Halin graphs

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$ such that all $n$ oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…     

A 3-approximation for the pathwidth of Halin graphs

We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.     

Subspace intersection graphs

Given a set R of affine subspaces in R^d of dimension e, its intersection graph G has a vertex for each subspace, and two vertices are adjacent in G if and only if their corresponding subspaces intersect. For each pair of positive integers d and e we obtain the class of (d,e)-subspace intersection graphs. We classify the classes of (d,e)-subspace intersection graphs by containment, for e=1 or e=d−1 or d≤4.     

Helly EPT graphs on bounded degree trees: Characterization and recognition

The edge-intersection graph of a family of paths on a host tree is called an $EPT$ graph. When the tree has maximum degree $h$, we say that the graph is $[h,2,2]$. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly $[h,2,2]$. In this paper, we present a family of $EPT$ graphs called gates which are forbidden induced subgraphs for $[h,2,2]$ graphs. Using these we characterize by forbidden induced subgraphs the Helly $[h,2,2]$ graphs. As a byproduct we prove that in getting a Helly $EPT$-representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly $[h,2,2]$ graphs based on their decomposition by maximal clique separators.     

Completely connected clustered graphs

Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e., hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.     

Halin图谱半径的新上界及极图

利用移接变形的方法再结合特征值的计算技巧刻画出Halin图中谱半径达到第二大的极图,从而得到除轮图以外的Halin图的谱半径的上界以及极图.     

A superclass of Edge-Path-Tree graphs with few cliques

Edge-Path-Tree (EPT) graphs are intersection graphs of EPT matrices that is matrices whose columns are incidence vectors of edge-sets of paths in a given tree. EPT graphs have polynomially many cliques [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinational Theory Series B 38 (1985) 8–22; C.L. Monma, V.K. Wey, Intersection graphs of paths in a tree, Journal of Combinational Theory Series B 41 (1986) 141–181]. Therefore, the problem of finding a clique of maximum weight in these graphs is solvable in strongly polynomial time. We extend this result to a proper superclass of EPT graphs.     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

Caterpillar arboricity of planar graphs

We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets (E_i)_1?i?4 in such a way that G[E_i], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G.     

Remarks on the bondage number of planar graphs

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented.     

Gromov hyperbolicity of periodic planar graphs

The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it.The main result in this paper is a very simple characterization of the hyperbolicity of a large class of periodic planar graphs.