Fishburn, Tanenbaum, and Trenk define the linear discrepancy $\text{Id}(P)$ of a poset $P=(V,{<}_P)$ as the minimum integer $k\ge 0$ for which there exists a bijection $f:V\to \{1,2,\dots ,|V|\}$ such that $u{<}_{P}v$ implies $f(u)<f(v)$ and $u|{|}_{P}v$ implies $|f(u)–f(v)|\le k$. In their work, they prove that the linear discrepancy of a poset equals the bandwidth of its cocomparability graph. Here we provide partial solutions to some problems formulated in their study about the linear discrepancy and the bandwidth of cocomparability graphs.

To date, investigations on critical sets for a set of mutually orthogonal Latin squares (MOLS) have been carried out only for small orders $\le 9$. In this paper, we deal with a pair of cyclic orthogonal Latin squares of order $n$, $n\ge 11$, $n$ odd. Through the construction of a uniquely completable set, we give an upper bound on the size of the minimal critical set. In particular, for $n=15$, a critical set achieving this bound is obtained.

We improve the lower bound for the $\alpha$-size of trees with maximum degree three.

A graph $G$ is called $(a,d)$-\text{edge antimagic total} $(a,d)$-\text{EAT} if there exist integers $a>0,d\ge 0$ and a bijection $\lambda :V\cup E\to \{1,2,\dots ,|V|+|E|\}$ such that

$$W=\{w(xy):xy\in E\}=\{a,a+d,\dots ,a+(|E|-1)d\},$$

where $w(xy)=\lambda (x)+\lambda (y)+\lambda (xy)$. An $(a,d)$-EAT labeling $\lambda$ of graph $G$ is \text{super} if $\lambda (V)=\{1,2,\dots ,|V|\}$. In this paper, we describe how to construct a super $(a,d)$-EAT labeling on some classes of disconnected graphs, namely $P_n\cup P_{n+1}$, $n{P}_2\cup P_n$, and $n{P}_2\cup P_{n+2}$, for positive integer $n$.

A graph $G(V,E)$ is called a sum graph if there is an injective labeling called sum labeling $L$ from $V$ to a set of distinct positive integers $S$ such that $xy\in E$ if and only if there is a vertex $w\in V$ such that $L(w)=L(x)+L(y)\in S$. In such a case, $w$ is called a working vertex. Every graph can be made into a sum graph by adding some isolated vertices, if necessary. The smallest number of isolated vertices that need to be added to a graph $H$ to obtain a sum graph is called the sum number of $H$; it is denoted by $\sigma (H)$. A sum labeling which realizes $H\cup \overline{K_{\sigma }(G)}$ as a sum graph is called an optimal sum labeling of $H$.

Sum graph labeling offers a new method for defining graphs and for storing them digitally. Traditionally, a graph is defined as a set of vertices and a set of edges, specified by pairs of vertices which are the endpoints of an edge. To record a graph on a computer, the edges are usually stored either in the form of an adjacency matrix or as a linked list. Using sum graph labeling, we only need to store the set of vertices, together with some additional isolates, if needed. While previously the edges in a graph were specified explicitly, using sum graphs, edges can be specified implicitly.

A sum labeling $L$ is called an exclusive sum labeling with respect to a subgraph $H$ of $G$ if $L$ is a sum labeling of $G$ where $H$ contains no working vertex. The exclusive sum number $ϵ(H)$ of a graph $H$ is the smallest number $r$ such that there exists an exclusive sum labeling $L$ which realizes $H\cup \overline{K_r}$ as a sum graph. A labeling $L$ is an optimal exclusive sum labeling of a graph $H$ if $L$ is a sum labeling of $H\cup K_{ϵ(H)}$ and $H$ contains no working vertex. While the exclusive sum number is never smaller than the corresponding sum number of a graph, labeling graphs exclusively has other desirable features which give greater scope for combining two or more labeled graphs.

In this paper, we introduce exclusive sum graph labeling and we construct optimal exclusive sum graph labeling for complete bipartite graphs, paths, and cycles. The paper concludes with a summary of known results in exclusive sum labeling and exclusive sum numbers for several classes of graphs.

A total vertex irregular labeling of a graph $G$ with $v$ vertices and $e$ edges is an assignment of integer labels to both vertices and edges so that the weights calculated at vertices are distinct. The total vertex irregularity strength of $G$, denoted by $tvs(G)$, is the minimum value of the largest label over all such irregular assignments. In this paper, we consider the total vertex irregular labeling of complete bipartite graphs $K_{m,n}$ and prove that

$$tvs(K_{m,n})\ge max\{\lceil \frac{m+n}{m+1}\rceil ,\lceil \frac{2m+n-1}{n}\rceil \}\text{if }(m,n)\ne (2,2).$$

For given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest natural number $n$ such that for every graph $F$ of order $n$: either $F$ contains $G$ or the complement of $F$ contains $H$.

This paper investigates the Ramsey number $R(S_n,W_m)$ of stars versus wheels. We show that if $m$ is odd, $n\ge 3$, and $m\le 2n-1$, then $R(S_n,W_m)=3n-2$. Furthermore, if $n$ is odd and $n\ge 5$, then $R(S_n,W_m)=3n–\mu$, where $\mu =4$ if $m=2n–4$ and $\mu =6$ if $m=2n–8$ or $m=2n–6$.

The notions of sum labeling and sum graph were introduced by Harary in 1990. In a sum labeling, a vertex is called a working vertex if its label is equal to the sum of the labels of a pair of two distinct vertices.

A sum labeling of a graph $G$ is said to be \text{exclusive} if it is a sum labeling of $G$ such that $G$ contains no working vertex. Any connected graph $G$ will require some additional isolated vertices in order to be labeled exclusively. The smallest number of such isolates is called the exclusive sum number of $G$; it is denoted by $ϵ(G)$. The number of isolates cannot be less than the maximum number of neighbors of any vertex in the graph, that is, at least equal to $\mathrm{\Delta }(G)$, the maximum vertex degree in $G$. If $ϵ(G)=\mathrm{\Delta }(G)$, then $G$ is said to be a $\mathrm{\Delta }$-\text{optimum summable graph}. An exclusive sum labeling of $G$ using $\mathrm{\Delta }(G)$ isolates is called a $\mathrm{\Delta }$-optimum exclusive sum labeling of $G$.

In this paper, we show that some families of trees are $\mathrm{\Delta }$-optimum summable graphs. However, this is not true for all trees, and we present an example of a tree that is not a $\mathrm{\Delta }$-optimum summable graph, giving rise to an open problem.

For graphs $G_1,G_2,\dots ,G_k$, the (generalized) \text{size multipartite Ramsey number} $m_j(G_1,G_2,\dots ,G_k)$ is the least natural number $m$ such that any coloring of the edges of $K_{j\times m}$ with $k$ colors will yield a copy of $G_i$ in the $i$th color for some $i$. In this note, we determine the exact value of the size multipartite Ramsey number $m_j(P_s,P_t)$ for $s=2,3$ and all integers $t\ge 2$, where $P_t$ denotes a path on $t$ vertices.

Let $G=(V,E)$ be a graph with $v$ vertices and $e$ edges. A $(a,d)$-\text{vertex-antimagic total labeling} is a bijection $\alpha$ from $V(G)\cup E(G)$ to the set of consecutive integers $1,2,\dots ,v+e$, such that the weights of the vertices form an arithmetic progression with the initial term $a$ and the common difference $d$. If $\alpha (V(G))=\{1,2,\dots ,v\}$, then we call the labeling a \text{super $(a,d)$-vertex antimagic total}. We study basic properties of such labelings and show how to construct such labelings for some families of graphs, such as paths, cycles, and generalized Petersen graphs. We also show that such labeling does not exist for certain families of graphs, such as cycles with at least one tail, trees with an even number of vertices, and all stars.

In this paper, we study the properties of super edge-magic total graphs. In particular, we propose some algorithms to construct new super edge-magic total graphs from the old ones. We also construct a super edge-magic total labeling on certain disconnected graphs, namely $P_n\cup P_{n+1}$, $n{P}_2\cup P_n$, and $n{P}_2\cup P_{n+2}$.

Let $G=G(v,e)$ be a finite simple graph with $v$ vertices and $e$ edges. An $(a,d)$-\text{edge-antimagic-vertex} (EAV) \text{labeling} is a one-to-one mapping $f:V(G)\to \{1,2,\dots ,v\}$ such that for every edge $xy\in E(G)$, the edge-weight set

$$\{f(x)+f(y)\mid xy\in E(G)\}=\{a,a+d,a+2d,\dots ,a+(e-1)d\}$$

for some positive integers $a$ and $d$. An $(a,d)$-\text{edge-antimagic-total labeling} is a one-to-one mapping $f:V(G)\cup E(G)\to \{1,2,\dots ,v+e\}$ with the property that for every edge $xy\in E(G)$,

$$\{f(x)+f(y)+f(xy)\mid xy\in E(G)\}=\{a,a+d,a+2d,\dots ,a+(e-1)d\}.$$

This labeling is called \text{super $(a,d)$-edge-antimagic total labeling} if $f(V(G))=\{1,2,\dots ,v\}$. In this paper, we investigate the relationship between the adjacency matrix, $(a,d)$-edge-antimagic vertex labeling, and super $(a,d)$-edge-antimagic total labeling, and show how to manipulate this matrix to construct new $(a,d)$-edge-antimagic vertex labelings and new super $(a,d)$-edge-antimagic total graphs.

A total labeling of a graph $G$ with $p$ vertices and $q$ edges is a one-to-one mapping from $V(G)\cup E(G)$ onto $\{1,2,\dots ,p+q\}$. If the edge-weights (resp. vertex-weights) form an arithmetic progression starting from $a$ and having common difference $d$, then the labeling is called an $(a,d)$-edge (resp. vertex) – antimagic total labeling. In this paper, we consider such labeling applied to the generalized Petersen graph.

A simple graph $G=(V,E)$ admits an $H$-\emph{covering} if every edge in $E$ belongs to a subgraph of $G$ isomorphic to $H$. In this case, we say that $G$ is $H$-\emph{magic} if there is a total labeling $f:V\cup E\to \{1,2,\dots ,|V|+|E|\}$ such that for each subgraph $H^{\prime }=(V^{\prime },E^{\prime })$ of $G$ isomorphic to $H$,

$$\sum _{v\in V^{\prime }}f(v)+\sum _{e\in E^{\prime }}f(e)$$

is constant. When $f(V)=\{1,\dots ,|V|\}$, we say that $G$ is $H$-\emph{supermagic}.

We study $H$-magic graphs for several classes of connected graphs. We also provide constructions of infinite families of $H$-magic graphs for an arbitrary given graph $H$.

Let $\lambda$ be an edge-magic total (EMT) labeling of graph $G(V,E)$. Let $W\subset V(G)\cup E(G)$. Any restriction of $\lambda$ to $W$ is called a \emph{partial EMT labeling} on $G$. A partial EMT labeling $\pi$ is a critical set in $\lambda$ if $\lambda$ is the only edge-magic total labeling having $\pi$ as its partial EMT labeling, and no proper restriction of $\pi$ satisfies the first condition. In this paper, we study the property of critical sets in such a labeling. We determine critical sets in an EMT labeling for a given graph $G$.

A $(p,q)$ graph $G$ is called edge-magic if there exists a bijective function $f:V(G)\cup E(G)\to \{1,2,\dots ,p+q\}$ such that $f(u)+f(v)+f(uv)$ is a constant for each edge $uv\in E(G)$. Also, $G$ is said to be super edge-magic if $f(V(G))=\{1,2,\dots ,p\}$. Furthermore, the super edge-magic deficiency, ${\mu }_s(G)$, of a graph $G$ is defined to be either the smallest nonnegative integer $n$ with the property that the graph $G\cup n{K}_1$ is super edge-magic or $+\mathrm{\infty }$ if there exists no such integer $n$.

In this paper, the super edge-magic deficiency of certain forests and 2-regular graphs is computed, which in turn leads to some conjectures on the super edge-magic deficiencies of graphs in these classes. Additionally, some edge-magic deficiency analogues to the super edge-magic deficiency results on forests are presented.

Suppose $G=(V,E,F)$ is a finite plane graph with vertex set $V(G)$, edge set $E(G)$, and face set $F(G)$. A bijection $\lambda :V(G)\cup E(G)\cup F(G)\to \{1,2,3,\dots ,|V(G)|+|E(G)|+|F(G)|\}$ is called a labeling of type $(1,1,1)$. The weight of a face under a labeling is the sum of the labels (if present) carried by that face and the edges and vertices surrounding it. A labeling of a plane graph $G$ is called $d$-\emph{antimagic} if for every number $s\ge 3$, the set of $s$-sided face weights is

$$W_s=\{a_s+id:0\le i\le f_s\}$$

for some integers $a_s$ and $d$ ($a>0$, $d\ge 0$), where $f_s$ is the number of $s$-sided faces. We allow different sets $W_s$ for different $s$.

In this paper, we deal with $d$-\emph{antimagic} labelings of type $(1,1,1)$ for a special class of plane graphs $C_a^b$ and we show that a $C_a^b$ graph has $d$-antimagic labeling for $d\in \{a-2,a-1,a+1,a+2\}$.

A $V(m,t)$ leads to $m$ idempotent pairwise orthogonal Latin squares of order $(m+1)t+1$ with one common hole of order $t$. $V(m,t)$’s can also be used to construct perfect Mendelsohn designs and optimal optical orthogonal codes. For $3\le m\le 8$, the spectrum for $V(m,t)$ has been determined. In this article, we investigate the existence of $V(m,t)$ with $m=9$ and show that a $V(9,t)$ always exists in $GF(q)$ for any prime power $q=9t+1$ with the exception of $q=73$ and one possible exception of $q=5^6$.

A Vertex Magic Total Labeling of a graph $G$ is a one-to-one map $\lambda$ from $E(G)\cup V(G)$ onto the set of integers $\{1,2,\dots ,e+v\}$ such that for all $x\in V$ we have

$$\lambda (x)+\sum \lambda (xy)=h$$

for some constant $h$, where the sum is taken over all vertices $y$ adjacent to $x$. In this paper, we present several theorems on the existence of such labelings for multipartite graphs and give constructions for labelings for two infinite families of complete tripartite graphs, namely $K_{1,n,n}$ for odd $n$ and $K_{2,n,n}$ for $n\equiv 3(\mathrm{mod}4)$.