Caterpillars with maximum degree 3 are antimagic

Let $G=(V,E)$ be a connected graph with $m$ edges. An antimagic labeling of $G$ is a one-to-one mapping from $E$ to $\{1,2,\dots ,m\}$ such that the vertex sum (i.e., sum of the labels assigned to edges incident to a vertex) for distinct vertices are different. A graph $G$ is called antimagic if $G$ has an antimagic labeling. It was conjectured by Hartsfield and Ringel that every tree other than $K_2$ is antimagic. The conjecture remains open though it was verified for trees with some constrains. Caterpillars are an important subclass of trees. This paper shows caterpillars with maximum degree 3 are antimagic, which gives an affirmative answer to an open problem of Lozano et al. (2019).     

An efficient distributed algorithm for canonical labeling on directed split-stars

We consider the problem of canonical labeling in anonymous directed split-stars. This paper proposes a distributed algorithm for finding the vertex sets with specified leading symbols in directed split-stars and which has a linear message and constant time complexity. The algorithm runs on an asynchronous timing model without shared memory. In addition, our algorithm generalizes the previous distributed algorithms on directed split-stars that we know.     

POPMUSIC for the point feature label placement problem

Point feature label placement is the problem of placing text labels adjacent to point features on a map so as to maximize legibility. The goal is to choose positions for the labels that do not give rise to label overlaps and that minimize obscuration of features. A practical goal is to minimize the number of overlaps while considering cartographic preferences. This article proposes a new heuristic for solving the point feature label placement problem based on the application of the POPMUSIC frame. Computational experiments show that the proposed heuristic outperformed other recent metaheuristics approaches in the literature. Experiments with problem instances involving up to 10 million points show that the computational time of the proposed heuristic increases almost linearly with the problem size. New problem instances based on real data with more than 13,000 labels are proposed.     

Super edge-magic strength of fire crackers, banana trees and unicyclic graphs

A graph G(V,E) is called super edge-magic if there exists a bijection f from V∪E to {1,2,3,…,|V|+|E|} such that f(u)+f(v)+f(uv)=c(f) is constant for any uv∈E and f(V)={1,2,3,…,|V|}. Such a bijection is called a super edge-magic labeling of G. The super edge-magic strength of a graph G is defined as the minimum of all c(f) where the minimum runs over all super edge-magic labelings of G and is denoted by sm(G). The super edge-magic strength of some families of graphs are obtained in this paper.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

New Approach for Fluorescent Peptide Labeling with Pyrylium Cyanine Dyes

New approach for fluorescent peptide labeling with cyanine dyes utilizing the reaction of pyrylium salts with aliphatic aminogroup is proposed. The reaction of two pyrylium cyanines dye acids was investigated. Lysocyme was used as a model peptide for conjugation. The proposed method can be used as a simple and convenient alternative for the known procedures because it does not require preparation of the unstable amino-reactive intermediates from a carboxyl- or sulfo-derivative of cyanine dyes.     

Orthogonal Double Covers of Complete Graphs by Caterpillars of Diameter 5

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection = {G_i|i = 1,2, . . . ,n} of spanning subgraphs of K_n, all isomorphic to G, with the property that every edge of K_n belongs to exactly two members of and any two distinct members of share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K_n.