Finding a core of a tree with pos/neg weight

Let T?=?(V, E) be a tree. A core of T is a path P, for which the sum of the weighted distances from all vertices to this path is minimized. In this paper, we consider the semi-obnoxious case in which the vertices have positive or negative weights. We prove that, when the sum of the weights of vertices is negative, the core must be a single vertex and that, when the sum of the vertices?? weights is zero there exists a core that is a vertex. Morgan and Slater (J Algorithms 1:247?C258, 1980) presented a linear time algorithm to find the core of a tree with only positive weights of vertices. We show that their algorithm also works for semi-obnoxious problems.     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

Antibandwidth of three-dimensional meshes

The antibandwidth problem is to label vertices of a graph G=(V,E) bijectively by 0,1,2,…,|V|−1 so that the minimal difference of labels of adjacent vertices is maximised. In this paper we prove an almost exact result for the antibandwidth of three-dimensional meshes. Provided results are extensions of the two-dimensional case and an analogue of the result for the bandwidth of three-dimensional meshes obtained by FitzGerald.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Improved bounds for the Laplacian energy of Bethe trees

For k, d?2, a Bethe tree is a rooted tree with k levels which the root vertex has degree d, the vertices from level 2 to k-1 have degree d+1 and the vertices at the level k are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees.     

An asymptotic bound for the complexity of monotone graph properties

We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ¼n ², proved in the same paper. In case that the evasiveness conjecture holds, it is ½n(n?1).We demonstrate some techniques to improve the 1/4 bound and show $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ?n ², proved in the same paper. In case that the evasiveness conjecture holds, it is ?n(n−1).We demonstrate some techniques to improve the 1/4 bound and show $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) .     

Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition \(E_1 \cup E_2 \cup \cdots \cup E_k\) of the edge set E(G) such that each \(E_i\) induces a locally irregular graph. It was recently conjectured by Baudon et al. that every undirected graph admits a decomposition into at most three locally irregular graphs, except for a well-characterized set of indecomposable graphs. We herein consider an oriented version of this conjecture. Namely, can every oriented graph be decomposed into at most three locally irregular oriented graphs, i.e. whose adjacent vertices have distinct outdegrees? We start by supporting this conjecture by verifying it for several classes of oriented graphs. We then prove a weaker version of this conjecture. Namely, we prove that every oriented graph can be decomposed into at most six locally irregular oriented graphs. We finally prove that even if our conjecture were true, it would remain NP-complete to decide whether an oriented graph is decomposable into at most two locally irregular oriented graphs.     

On sequential labelings of graphs

A valuation on a simple graph G is an assignment of labels to the vertices of G which induces an assignment of labels to the edges of G. β-valuations, also called graceful labelings, and α-valuations, a subclass of graceful labelings, have an extensive literature; harmonious labelings have been introduced recently by Graham and Sloane. This paper introduces sequential labelings, a subclass of harmonious labelings, and shows that any tree admitting an α-valuation also admits a sequential labeling and hence is harmonious. Constructions are given for new families of graceful and sequential graphs, generalizing some earlier results. Finally, a conjecture of Frucht is shown to be wrong by exhibiting several graceful labelings of wheels in which the center label is larger than previously thought possible.     

An approximate version of Sumner?s universal tournament conjecture

Sumner?s universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.     

Memetic algorithm for the antibandwidth maximization problem

The antibandwidth maximization problem (AMP) consists of labeling the vertices of a n-vertex graph G with distinct integers from 1 to n such that the minimum difference of labels of adjacent vertices is maximized. This problem can be formulated as a dual problem to the well known bandwidth problem. Exact results have been proved for some standard graphs like paths, cycles, 2 and 3-dimensional meshes, tori, some special trees etc., however, no algorithm has been proposed for the general graphs. In this paper, we propose a memetic algorithm for the antibandwidth maximization problem, wherein we explore various breadth first search generated level structures of a graph—an imperative feature of our algorithm. We design a new heuristic which exploits these level structures to label the vertices of the graph. The algorithm is able to achieve the exact antibandwidth for the standard graphs as mentioned. Moreover, we conjecture the antibandwidth of some 3-dimensional meshes and complement of power graphs, supported by our experimental results.     

A note on Barnette’s conjecture

A well-known conjecture of Barnette states that every 3-connected cubic bipartite planar graph has a Hamiltonian cycle, which is equivalent to the statement that every 3-connected even plane triangulation admits a 2-tree coloring, meaning that the vertices of the graph have a 2-coloring such that each color class induces a tree. In this paper we present a new approach to Barnette’s conjecture by using 2-tree coloring.A Barnette triangulation is a 3-connected even plane triangulation, and a B-graph is a smallest Barnette triangulation without a 2-tree coloring. A configuration is reducible if it cannot be a configuration of a B-graph. We prove that certain configurations are reducible. We also define extendable, non-extendable and compatible graphs; and discuss their connection with Barnette’s conjecture.     

On generalized Petersen graphs labeled with a condition at distance two

An L(2,1)-labeling of graph G is an integer labeling of the vertices in V(G) such that adjacent vertices receive labels which differ by at least two, and vertices which are distance two apart receive labels which differ by at least one. The λ-number of G is the minimum span taken over all L(2,1)-labelings of G. In this paper, we consider the λ-numbers of generalized Petersen graphs. By introducing the notion of a matched sum of graphs, we show that the λ-number of every generalized Petersen graph is bounded from above by 9. We then show that this bound can be improved to 8 for all generalized Petersen graphs with vertex order >12, and, with the exception of the Petersen graph itself, improved to 7 otherwise.     

Undirected forest constraints

We present two constraints that partition the vertices of an undirected n-vertex, m-edge graph \(\mathcal {G}=( \mathcal {V}, \mathcal {E})\) into a set of vertex-disjoint trees. The first is the resource-forest constraint, where we assume that a subset \(\mathcal {R}\subseteq \mathcal {V}\) of the vertices are resource vertices. The constraint specifies that each tree in the forest must contain at least one resource vertex. This is the natural undirected counterpart of the tree constraint (Beldiceanu et al., CP-AI-OR’05, Springer, Berlin, 2005), which partitions a directed graph into a forest of directed trees where only certain vertices can be tree roots. We describe a hybrid-consistency algorithm that runs in \(\mathop {\mathcal {O}}(m+n)\) time for the resource-forest constraint, a sharp improvement over the \(\mathop {\mathcal {O}}(mn)\) bound that is known for the directed case. The second constraint is proper-forest. In this variant, we do not have the requirement that each tree contains a resource, but the forest must contain only proper trees, i.e., trees that have at least two vertices each. We develop a hybrid-consistency algorithm for this case whose running time is \(\mathop {\mathcal {O}}(mn)\) in the worst case, and \(\mathop {\mathcal {O}}(m\sqrt{n})\) in many (typical) cases.     

On deletions of largest bonds in graphs

A well-known conjecture of Scott Smith is that any two distinct longest cycles of a k-connected graph must meet in at least k vertices when k≥2. We provide a dual version of this conjecture for two distinct largest bonds in a graph. This dual conjecture is established for k?6.     

The spum and sum-diameter of graphs: Labelings of sum graphs

A sum graph is a finite simple graph whose vertex set is labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label. The spum of a graph G is the minimum difference between the largest and smallest labels in a sum graph consisting of G and the minimum number of additional isolated vertices necessary so that a sum graph labeling exists. We investigate the spum of various families of graphs, namely cycles, paths, and matchings. We introduce the sum-diameter, a modification of the definition of spum that omits the requirement that the number of additional isolated vertices in the sum graph is minimal, which we believe is a more natural quantity to study. We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph operations as well as vertex and edge operations. Finally, we generalize the sum-diameter to hypergraphs.     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.     

The Estrada index of trees

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of its adjacency matrix. We determine the unique tree with maximum Estrada index among the set of trees with given number of pendant vertices. As applications, we determine trees with maximum Estrada index among the set of trees with given matching number, independence number, and domination number, respectively. Finally, we give a proof of a conjecture in [J. Li, X. Li, L. Wang, The minimal Estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem. 64 (2010) 799-810] on trees with minimum Estrada index among the set of trees with two adjacent vertices of maximum degree.     

Labeling trees with a condition at distance two

An L(h,k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h,k)-labeling is the difference between the largest and the smallest label. We investigate L(h,k)-labelings of trees of maximum degree Δ, seeking those with small span. Given Δ, h and k, span λ is optimal for the class of trees of maximum degree Δ, if λ is the smallest integer such that every tree of maximum degree Δ has an L(h,k)-labeling with span at most λ. For all parameters Δ,h,k, such that h<k, we construct L(h,k)-labelings with optimal span. We also establish optimal span of L(h,k)-labelings for stars of arbitrary degree and all values of h and k.     

A note on the cubical dimension of new classes of binary trees

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 ⁿ vertices, n ? 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.     

Variable neighborhood search with ejection chains for the antibandwidth problem

In this paper, we address the optimization problem arising in some practical applications in which we want to maximize the minimum difference between the labels of adjacent elements. For example, in the context of location models, the elements can represent sensitive facilities or chemicals and their labels locations, and the objective is to locate (label) them in a way that avoids placing some of them too close together (since it can be risky). This optimization problem is referred to as the antibandwidth maximization problem (AMP) and, modeled in terms of graphs, consists of labeling the vertices with different integers or labels such that the minimum difference between the labels of adjacent vertices is maximized. This optimization problem is the dual of the well-known bandwidth problem and it is also known as the separation problem or directly as the dual bandwidth problem. In this paper, we first review the previous methods for the AMP and then propose a heuristic algorithm based on the variable neighborhood search methodology to obtain high quality solutions. One of our neighborhoods implements ejection chains which have been successfully applied in the context of tabu search. Our extensive experimentation with 236 previously reported instances shows that the proposed procedure outperforms existing methods in terms of solution quality.