Let G be a graph, and ℓ:E(G)→{1,…,k} be a k-labelling of G, i.e., an assignment of labels from {1,…,k} to the edges of G. We say that ℓ is irregular if no two distinct vertices of G are incident to ...the same sum of labels. The irregularity strength of G, denoted by s(G), is the smallest k such that irregular k-labellings of G exist. These notions were introduced in the late 1980s as an alternative way to deal with an optimisation problem where one aims at making a graph irregular by multiplying its edges in an optimal way. Since then, the irregularity strength has received a lot of attention, focusing mainly on proving bounds and investigating side aspects and variants.
In this work, we consider the algorithmic complexity of determining the irregularity strength of a given graph. We prove that two close variants of this problem are NP-hard, which we suspect might indicate that the original problem is hard too. Namely, we prove that determining the distant irregularity strength, where only vertices within a certain distance are required to be incident to different sums of labels, and the multiset irregularity strength, where any two distinct vertices are required to be incident to different multisets of labels, are NP-hard problems.
The sumset of two sets A and B of integers, denoted by A + B, is defined as A+B = {a+b : a ∈ A, b ∈ B}. Let X be a non-empty set of non-negative integers. A sumset labelling of a graph G is an ...injective function f : V (G) → P(X) − {∅} such that the induced function f+ : E(G) → P(X)−{∅} is defined by f+(uv) = f(u) +f(v) ∀uv ∈ E(G). In this paper, we introduce the notion of ideal sumset labelling of graph and discuss the admissibility of this labelling by certain graph classes and discuss some structural characterization of those graphs.
To cut or to fill Zeng, Dan; Chambers, Erin; Letscher, David ...
ACM transactions on graphics,
11/2020, Letnik:
39, Številka:
6
Journal Article
Recenzirano
Odprti dostop
We present a novel algorithm for simplifying the topology of a 3D shape, which is characterized by the number of connected components, handles, and cavities. Existing methods either limit their ...modifications to be only cutting or only filling, or take a heuristic approach to decide where to cut or fill. We consider the problem of finding a globally optimal set of cuts and fills that achieve the simplest topology while minimizing geometric changes. We show that the problem can be formulated as graph labelling, and we solve it by a transformation to the Node-Weighted Steiner Tree problem. When tested on examples with varying levels of topological complexity, the algorithm shows notable improvement over existing simplification methods in both topological simplicity and geometric distortions.
A sum graph G is a graph with a mapping of the vertex set of G onto a set of positive integers S in such a way that two vertices of G are adjacent if and only if the sum of their labels is an element ...of S. In an exclusive sum graph the integers of S that are the sum of two other integers of S form a set of integers that label a collection of isolated vertices associated with the graph G. A graph bears a k-exclusive sum labelling (abbreviated k-ESL), if the set of isolated vertices is of cardinality k.
In this paper, observing that the property of having a k-ESL is hereditary, we provide a characterisation of graphs that have a k-exclusive sum labelling, for any k≥1, in terms of describing a universal graph for the property.
We consider two recent conjectures made by Harrington, Henninger-Voss, Karhadkar, Robinson and Wong concerning relationships between the sum index, difference index and exclusive sum number of ...graphs. One conjecture posits an exact relationship between the first two invariants; we show that in fact the predicted value may be arbitrarily far from the truth in either direction. In the process we establish some new bounds on both the sum and difference index. The other conjecture, that the exclusive sum number can exceed the sum index by an arbitrarily large amount, follows from known, but non-constructive, results; we give an explicit construction demonstrating it. Simultaneously with the first preprint of this paper appearing, Harrington et al. updated their preprint with two counterexamples to the first conjecture; however, their counterexamples only give a discrepancy of 1, and only in one direction. They therefore modified the conjecture from an equality to an inequality; our results show that this is still false in general.
λ–Core distance partitions Mifsud, Xandru
Linear algebra and its applications,
03/2021, Letnik:
613
Journal Article
Recenzirano
Odprti dostop
The λ–core vertices of a graph correspond to the non–zero entries of some eigenvector of λ for a universal adjacency matrix U of the graph. We define a partition of the vertex set V based on the ...λ–core vertex set and its neighbourhoods at a distance r, and give a number of results relating the structure of the graph to this partition. For such partitions, we also define an entropic measure for the information content of a graph, related to every distinct eigenvalue λ of U, and discuss its properties and potential applications.
In a graph G = (V, E), L(2, 1)-labelling is considered by a function l whose domain is V and codomain is set of non-negative integers with a condition that the vertices which are adjacent assign ...labels whose difference is at least two and the vertices whose distance is two, assign distinct labels. The difference between maximum and minimum labels among all possible labels is denoted by lambda.sub.2,1 (G). This paper contains a variant of L(2, 1)-labelling problem. In L(2, 1)-labelling problem, all the vertices are L(2, 1)-labeled by least number of labels. In this paper, maximum allowable label K is given. The problem is: L(2, 1)-label the vertices of G by using the labels {0,1,2,..., K} such that maximum number of vertices get label. If K labels are adequate for labelling all the vertices of the graph then all vertices get label, otherwise some vertices remains unlabeled. An algorithm is designed to solve this problem. The algorithm is also illustrated by examples. Also, an algorithm is designed to test whether an interval graph is no hole label or not for the purpose of L(2, 1)-labelling. Keyword: Interval graph, graph labelling, L(2, 1)-labelling, holes in label. AMS Subject Classification: 05C.sub.40, 05C62.
Given a graph G, the zero forcing number of G, Z(G), is the smallest cardinality of any set S of vertices on which repeated applications of the forcing rule results in all vertices being in S. The ...forcing rule is: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. In this paper, we investigate the largest size of a set S that does not force all of the vertices in a graph to be in S. This quantity is known as the failed zero forcing number of a graph and will be denoted by F(G). We present new results involving this parameter. In particular, we completely characterize all graphs G where F(G)=2, solving a problem posed in 2015 by Fetcie, Jacob, and Saavedra.
Two new graph characteristics, the total vertex irregularity strength and the total edge irregularity strength, are introduced. Estimations on these parameters are obtained. For some families of ...graphs the precise values of these parameters are proved.
PDF
