In a previous work, we defined and studied random walk labelings of graphs. These are graph labelings that are obtainable by performing a random walk on the graph, such that each vertex is labeled ...upon its first visit. In this work, we calculate the number of random walk labelings of several natural graph families: The wheel, fan, barbell, lollipop, tadpole, friendship, and snake graphs. Additionally, we prove several combinatorial identities that emerged during the calculations.
Abstract
In this paper a new variant of divisor cordial labeling (DCL) named double divisor cordial labeling (DDCL) is in-troduced. A DDCL of a graph
G
ω
having a node set
V
ω
is a bijection
g
ω
from
...V
ω
to {1,2,3,…, |
V
ω
|} such that each edge
yz
is given the label 1 if 2
g
ω
(
y
)/
g
ω
(
z
) or 2
g
ω
(
z
)/
g
ω
(
y
) and 0 otherwise, then the modulus of difference of edges labeled 0 and those labeled 1 do not exceed 1 i.e; |
e
g
ω
(0) —
e
g
ω
(1)| ≤ 1. If a graph permits a DDCL, then it is known as double divisor cordial graph (DDCG). In this paper we derive certain general results concerning DDCL and establish the same for some well known graphs.
A vertex in-out-antimagic total labeling of a directed graph (digraph) D=(V,A) with n vertices and m arcs is a bijection from the set V∪A to the set of integers {1,2,…,m+n} such that all n vertex ...in-weights are pairwise distinct and simultaneously all n vertex out-weights are pairwise distinct. The vertex in-weight is the sum of the vertex label and the labels of all incoming arcs and the vertex out-weight is the sum of the vertex label and the labels of all outgoing arcs.
In this paper we provide a general way how to label dense digraphs and certain sparse digraphs. Further, we add constructions of the labeling for three large infinite classes of digraphs and we conjecture that all digraphs allow such a labeling.
Suppose that G = (V (G), E(G)) is a graph and |V (G)| = p. If there exists a bijective function f : V (G) → {1, 2, 3, ..., p} such that an f c : E(G) → N defined by f c(uv) = (f(u)f(v))when f (u) > ...f(v) and f c(uv) = (f(u)f(v))when f (v) > f (u) is an injection function, then f is called a combination labelings and G is called a combination graph. This article considers a suitable bijective function f and prove that G(Cn, Cm, Pk) which are graphs related to two cycles and one path containing three parameters, are combination graphs.
The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn with n=|V(G)| vertices in such a way that the maximum number of overlapping edges (i.e., ...the congestion) is minimized. A graph G with a cutwidth of k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k>1. We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs.
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.
PDF
