Face Antimagic Labeling of Jahangir Graph

This paper deals with the problem of labeling the vertices, edges and faces of a plane graph. A weight of a face is the sum of the label of a face and the labels of the vertices and edges surrounding that face. In a super d-antimagic labeling the vertices receive the smallest labels and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s that appearing in the graph. The paper examines the existence of super d-antimagic labelings for Jahangir graphs for certain differences d.     

Face labelings of Klein-bottle fullerenes

The Klein-bottle fullerene is a finite trivalent graph embedded on the Klein-bottle such that each face is a hexagon. The paper deals with the problem of labeling the vertices, edges and faces of the Klein-bottle fullerene in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face and the weights of all 6-sided faces constitute an arithmetic progression of difference d. In this paper we study the existence of such labelings for several differences d.     

Labelings of plane graphs containing Hamilton path

This paper deals with the problem of labeling the vertices, edges and faces of a plane graph. A weight of a face is the sum of the label of a face and the labels of the vertices and edges surrounding that face. In a super d-antimagic labeling the vertices receive the smallest labels and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s appearing in the graph.     

Super d-antimagic labelings of disconnected plane graphs

This paper deals with the problem of labeling the vertices, edges and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s that appears in the graph. The paper examines the existence of such labelings for disjoint union of plane graphs.     

Vertex-antimagic labelings of regular graphs

Let G = (V, E) be a finite, simple and undirected graph with p vertices and q edges. An (a, d)-vertex-antimagic total labeling of G is a bijection f from V (G) ∪ E(G) onto the set of consecutive integers 1, 2, . . . , p + q, such that the vertex-weights form an arithmetic progression with the initial term a and difference d, where the vertex-weight of x is the sum of the value f (x) assigned to the vertex x together with all values f (xy) assigned to edges xy incident to x. Such labeling is called super if the smallest possible labels appear on the vertices. In this paper, we study the properties of such labelings and examine their existence for 2r-regular graphs when the difference d is 0, 1, . . . , r + 1.     

Total Edge Irregularity Strength of Toroidal Fullerene

A toroidal fullerene (toroidal polyhex) is a cubic bipartite graph embedded on the torus such that each face is a hexagon. An edge irregular total k-labeling of a graph G is such a labeling of the vertices and edges with labels 1, 2, … , k that the weights of any two different edges are distinct, where the weight of an edge is the sum of the label of the edge itself and the labels of its two endvertices. The minimum k for which the graph G has an edge irregular total k-labeling is called the total edge irregularity strength, tes(G). In this paper we determine the exact value of the total edge irregularity strength of toroidal polyhexes.     

A new graceful labeling for pendant graphs

A graceful labeling of a graph G with q edges is an injective assignment of labels from {0, 1, . . . , q} to the vertices of G so that when each edge is assigned the absolute value of the difference of the vertex labels it connects, the resulting edge labels are distinct. A labeling of the first kind for coronas ${C_n \odot K_1}$ occurs when vertex labels 0 and q = 2n are assigned to adjacent vertices of the n-gon. A labeling of the second kind occurs when q = 2n is assigned to a pendant vertex. Previous research has shown that all coronas ${C_n \odot K_1}$ have a graceful labeling of the second kind. In this paper we show that all coronas ${C_n \odot K_1}$ with ${n \equiv 3, 4\, {\rm (mod\, 8)}}$ also have a graceful labeling of the first kind.     

Super-vertex-antimagic total labelings of disconnected graphs

Let G=(V,E) be a finite, simple and non-empty (p,q)-graph of order p and size q. An (a,d)-vertex-antimagic total labeling is a bijection f from V(G)∪E(G) onto the set of consecutive integers 1,2,…,p+q, such that the vertex-weights form an arithmetic progression with the initial term a and the common difference d, where the vertex-weight of x is the sum of values f(xy) assigned to all edges xy incident to vertex x together with the value assigned to x itself, i.e. f(x). Such a labeling is called super if the smallest possible labels appear on the vertices.In this paper, we will study the properties of such labelings and examine their existence for disconnected graphs.     

Antimagic labeling of generalized pyramid graphs

An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.     

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.     

Interleaving schemes on circulant graphs with two offsets

Interleaving is used for error-correcting on a bursty noisy channel. Given a graph G describing the topology of the channel, we label the vertices of G so that each label-set is sufficiently sparse. The interleaving scheme corrects for any error burst of size at most t; it is a labeling where the distance between any two vertices in the same label-set is at least t.We consider interleaving schemes on infinite circulant graphs with two offsets 1 and d. In such a graph the vertices are integers; edge ij exists if and only if |i−j|∈{1,d}. Our goal is to minimize the number of labels used.Our constructions are covers of the graph by the minimal number of translates of some label-set S. We focus on minimizing the index of S, which is the inverse of its density rounded up. We establish lower bounds and prove that our constructions are optimal or almost optimal, both for the index of S and for the number of labels.     

On anti-magic labeling for graph products

An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K₂ are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.     

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.     

Equitable labelings of cycles

Every labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge (x, y) is the absolute value of the difference of the labels of x and y. By analogy with graceful labelings, we say that a labeling of the vertices of a graph of order n is minimally k-equitable if the vertices are labeled with 1,2,…, n and in the induced labeling of its edges every label either occurs exactly k times or does not occur at all. Bloom [3] posed the following question: Is the condition that k is a proper divisor of n sufficient for the cycle C_n to have a minimal k-equitable labeling? We give a positive answer to this question. © 1993 John Wiley & Sons, Inc.     

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.     

三路树P(m,n,t)是边幻图的证明(II)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

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.     

On the distribution of range for tree-indexed random walks

We study tree-indexed random walks as introduced by Benjamini, Häggström, and Mossel, i.e., labelings of a tree for which adjacent vertices have labels differing by 1. It is a conjecture of those authors that the distribution of the range for any such tree is dominated by that of a path on the same number of edges. The two main variants of this conjecture considered in the literature are the standard walks, in which adjacent vertices must have labels differing by exactly 1, and lazy walks, in which adjacent vertices must have labels differing by at most 1. We confirm this conjecture for all trees in the lazy case and provide some partial results in the standard case.     

Distance and routing labeling schemes for non-positively curved plane graphs

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this paper we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.     

Centrally symmetric polytopes with many faces

We present explicit constructions of centrally symmetric polytopes with many faces: (1) we construct a d-dimensional centrally symmetric polytope P with about 3 ^d/4 ≈ (1.316) ^d vertices such that every pair of non-antipodal vertices of P spans an edge of P, (2) for an integer k ≥ 2, we construct a d-dimensional centrally symmetric polytope P of an arbitrarily high dimension d and with an arbitrarily large number N of vertices such that for some 0 < δ _k < 1 at least (1 ? (δ _k ) ^d )( _k ^N ) k-subsets of the set of vertices span faces of P, and (3) for an integer k ≥ 2 and α > 0, we construct a centrally symmetric polytope Q with an arbitrarily large number of vertices N and of dimension d = k ^1+o(1) such that at least $(1 - k^{ - \alpha } )(_k^N )$ k-subsets of the set of vertices span faces of Q.