Narrow Results

The graph $K_1$ is a trivial graph consisting of a single vertex with no edges. In contrast, the graph $K_{1,\lambda }$ is a complete bipartite graph with one internal node and $\lambda$ leaf vertices. The join of two graphs $K_1$ and $K_{1,\lambda }$ (with central vertex ${\rho }_0$), represented as $K_1+K_{1,\lambda }$, is a graph including vertices $V(K_1+K_{1,\lambda })=V(K_1)\cup V(K_{1,\lambda })$ and edges $V(K_1+K_{1,\lambda })=V(K_1)\cup V(K_{1,\lambda })\cup \{{\sigma }_1{\rho }_0:{\sigma }_1\in V(K_1),{\rho }_0\in V(K_{1,\lambda })\}$. When two graphs, $K_1$ and $K_{1,\lambda }$ are joined, the result is a graph in which vertex in graph $K_1$ is linked to every vertex in graph $K_{1,\lambda }$. Modular multiplicative divisor (MMD) labeling is a vertex and edge labeling scheme with the following key features: Vertex labeling: MMD labeling establishes a bijection between the vertices of the graph $T$ and the natural numbers from 1 to $\left|v\right|$. This bijection ensures a one-to-one correspondence, providing a unique label for each vertex. Edge labeling: The labeling of edges follows a specific rule, the edge’s label is determined by calculating the result of multiplying the labels assigned to its connected vertices, with the outcome adjusted by modulo $n$. We demonstrate the modular multiplication labeling when combining two graphs through their join (assuming $\lambda$ is even) and also on the even arbitrary super subdivision (EASS) of the join of two graphs. Additionally, we explore a related research question that arises in this particular context. The findings have potential applications in network topology design and optimization.

A graph $G=(V,E)$ is considered antimagic if it admits antimagic labeling. The antimagic labeling of a finite, simple graph with $\left|V\right|=n$ and $\left|E\right|=m$ is a bijective function from the set of edges to the set of integers $\{1,2,\dots ,m\}$ such that the vertex sum of $n$ vertices is pairwise distinct. The vertex sum of a vertex is obtained by summing the labels of all edges incident to it. Hartsfield and Ringel conjectured that every connected graph different from $K_2$ is antimagic. Supporting this conjecture, it was shown that the dense graphs are antimagic. A cactus graph is a connected graph where no edge lies within more than one cycle. A cactus graph in which each block is a cycle of the same size $n$ is called an n-uniform cactus graph. We proved that Hartsfield and Ringel’s conjecture is true for $n$-uniform cactus chain graphs with and without pendant vertices, which are specific cases of sparse graphs.

The notion of κ-tameness of a pseudovariety was introduced by Almeida and Steinberg and is a strong property which implies decidability of pseudovarieties. In this paper we prove that the pseudovariety LSl, of local semilattices, is κ-tame.

Reconstruction of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. Some recent methods have been developed to reconstruct pedigrees using genotype data only. These methods are accurate and efficient for simple pedigrees which contain only siblings, where two individuals share the same pair of parents. A most recent method IPED2 is able to handle complicated pedigrees with half-sibling relationships, where two individuals share only one parent. However, the method is shown to miss many true positive half-sibling relationships as it removes all suspicious half-sibling relationships during the parent construction process. In this work, we propose a novel method IPED2X, which deploys a more robust algorithm for parent construction in the pedigrees by considering more possible operations rather than simple deletion. We convert the parent construction problem into a graph labeling problem and propose a more effective labeling algorithm. We show in our experiments that IPED2X is more powerful on capturing the true half-sibling relationships, which further leads to better reconstruction accuracy.

Graph labeling deals with assigning labels to one or more elements of a graph. It has a wide variety of applications including: coding theory, communication network addressing, data base management system and secret sharing schemes to mention a view. A mapping $\lambda$ is called a sum labeling of a graph $H(V(H),E(H))$ if it is an injection from $V(H)$ to a set of positive integers, such that $\{x,y\}\in E(H)$ if and only if there exists a vertex $w\in V(H)$ such that $\lambda (w)=\lambda (x)+\lambda (y)$. In this case, $w$ is called a working vertex. In general, a graph $G$ will require some isolated vertices to be labeled in this way. The least possible number of such isolated vertices is called the sum number of $G$; denoted by $\sigma (G)$.

A sum labeling of a graph $G$ is said to be optimum if it labels $G$ by using $\sigma (G)$ isolated vertices.

In this paper, we investigate the lower bounds for the number of isolates required by an even fan and an odd fan, and then we construct optimum sum labelling for the graphs to prove:

A total edge irregular $k$-labeling of a graph $G=(V,E)$, $\partial :V\cup E\to \{1,2,3,\dots ,k\}$ is a labeling of vertices and edges of $G$ in such a way that the weights of all edges are distinct. A total edge irregularity strength of graph $G$, denoted by $\mathrm{\text{tes}}(G)$ is defined as the minimum $k$ for which a graph $G$ has a totally irregular total $k$-labeling. In this paper, we define $(a,d)$-total edge irregularity labeling and provide the irregularity strength for some well-known families of graphs.