Sum index and difference index of graphs Harrington, Joshua; Henninger-Voss, Eugene; Karhadkar, Kedar ...
Discrete Applied Mathematics,
01/2023, Volume:
325
Journal Article
Peer reviewed
Open access
Let G be a nonempty simple graph with a vertex set V(G) and an edge set E(G). For every injective vertex labeling f:V(G)→Z, there are two induced edge labelings, namely f+:E(G)→Z defined by ...f+(uv)=f(u)+f(v), and f−:E(G)→Z defined by f−(uv)=|f(u)−f(v)|. The sum index and the difference index are the minimum cardinalities of the ranges of f+ and f−, respectively. We provide upper and lower bounds on the sum index and difference index, and determine the sum index and difference index of various families of graphs. We also provide an interesting conjecture relating the sum index and the difference index of graphs.
With the rapid development of quantum computing theory and quantum computer technology, the traditional public-key cryptographic algorithms face great challenges. A technology that might be able to ...resist attacks equipped with AI technique and quantum computers is the topological graphic password of topological coding. In order to further study topological coding, we use the multiple constraints of graph colorings and labelings to propose new techniques made by felicitous-type labelings and parameterizing felicitous-type labelings of graph theory. We show the RANDOMLY-LEAF-adding algorithm and some connections between felicitous-type labelings and parameterizing felicitous-type labelings since they can be applied to building up graphic lattices.
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.
In this article we introduce the notion of weak harmonic labeling of a graph, a generalization of the concept of harmonic labeling defined recently by Benjamini, Cyr, Procaccia and Tessler that ...allows extension to finite graphs and graphs with leaves. We present various families of examples and provide several constructions that extend a given weak harmonic labeling to larger graphs. In particular, we use finite weak models to produce new examples of (strong) harmonic labelings. As a main result, we provide a characterization of weakly labeled graphs in terms of harmonic subsets of Z and exhibit quantitative evidence of the efficiency of this method for computing all weakly labeled finite graphs as opposed to an exhaustive search calculation. In particular, we characterize harmonically labeled graphs as defined by Benjamini et al. We further extend the definitions and main results to the case of multigraphs and total labelings.
A positive integer n is a super totient number if the set of positive integers less than n and relatively prime to n can be partitioned into two sets of equal sum. In this article, we give a complete ...classification of super totient numbers. We also utilize super totient numbers to consider graph labelings. Let G be a graph with vertex set V and edge set E. For every injective vertex labeling f:V→N, define f∗:E→N and f+:E→N such that f∗(uv)=f(u)f(v) and f+(uv)=f(u)+f(v). We say f is a super totient labeling if f∗(uv) is a super totient number for every uv∈E. Moreover, if the range of a super totient labeling f is {1,2,…,|V|}, then f is said to be a restricted super totient labeling. The concept of super totient numbers was first introduced in 2017 by Mahmood and Ali, and they showed that every graph admits a super totient labeling. We classify all restricted super totient complete bipartite graphs, trees, wheel graphs, and friendship graphs. Furthermore, we introduce the sum index of a graph G, which is the minimum positive integer k such that there exists an injective vertex labeling f of G with the cardinality of the range of f+ being k. We show that the sum index is related to the concept of super totient labelings, and we determine the sum index of complete graphs, complete bipartite graphs, and certain families of trees such as caterpillar graphs.
In this work we consider
temporal networks
, i.e. networks defined by a
labeling
λ
assigning to each edge of an
underlying graph
G
a set of
discrete
time-labels. The labels of an edge, which are ...natural numbers, indicate the discrete time moments at which the edge is available. We focus on
path problems
of temporal networks. In particular, we consider
time-respecting
paths, i.e. paths whose edges are assigned by
λ
a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a
natural analogue of Menger’s theorem
holding for arbitrary temporal networks. Finally, we propose two
cost minimization parameters
for temporal network design. One is the
temporality
of
G
, in which the goal is to minimize the maximum number of labels of an edge, and the other is the
temporal cost
of
G
, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some
connectivity constraint
. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.
PDF
