The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...

A graph with p vertices is said to be strongly multiplicative if its vertices can be labelled 1,2,...,p so that the values on the edges, obtained as the product of the labels of their end vertices, are all distinct. In this paper, we study structural properties of strongly multiplicative graphs. We show that all graphs in some classes, including all trees, are strongly multiplicative, and consider the question of the maximum number of edges in a strongly multiplicative graph of a given order.

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph ${}_{d̲,\left[d̅\right]}\left(S\right)=(V,)$ where V = S and $=e\subseteq S:d̲\le \left|e\right|\le \left[d̅\right]\wedge {\sum }_{v\in e}v\in S$. For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y₁,...,y_{\sigma }\notin V$ such that $\cup y₁,...,y_{\sigma }$ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings for this...

A graph is called supermagic if it admits a labeling of the edges by pairwise different consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we establish some conditions for graphs with a saturated vertex to be supermagic. Inter alia we show that complete multipartite graphs K1,n,n and K1,2,...,2 are supermagic.

The study of valuations of graphs is a relatively young part of graph theory. In this article we survey what is known about certain graph valuations, that is, labeling methods: antimagic labelings, edge-magic total labelings and vertex-magic total labelings.

Let $G$ be a quasigroup. Associativity of the operation on $G$ can be expressed by the symbolic identity $R_x{L}_y=L_y{R}_x$ of left and right multiplication maps; likewise, commutativity can be expressed by the identity $L_x=R_x$. In this article, we investigate symmetric linear identities: these are identities in left and right multiplication symbols in which every indeterminate appears exactly once on each side, and whose sides are mirror images of each other. We determine precisely which identities imply associativity and...

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures...

An edge ordering of a graph G is an injection f : E(G) → R, the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f-ascent ; an f-ascent is maximal if it is not contained in a longer f-ascent. The depression of G is the smallest integer k such that any edge ordering f has a maximal f-ascent of length at most k. A k-kernel of a graph G is a set of vertices U ⊆ V (G) such that for any edge ordering f of G there exists a maximal f-ascent of...

If $G$ is a connected graph of order $n\ge 1$, then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V\left(G\right)$ into the set of all positive integers such that $|c\left(x\right)-c\left(y\right)|\ge n-1-D_G(x,y)$ (where $D_G(x,y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x,y\in V\left(G\right)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $$min(max(c\left(z\right);z\in V\left(G\right)\left)\right),$$ where the minimum is taken over all hamiltonian colorings $c$ of $G$. The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n\ge 3$. Assume that there exists a subgraph...

For a nontrivial connected graph $G$ of order $n$, the detour distance $D(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a longest $u-v$ path in $G$. Detour distance is a metric on the vertex set of $G$. For each integer $k$ with $1\le k\le n-1$, a coloring $c:V\left(G\right)\to \mathbb{N}$ is a $k$-metric coloring of $G$ if $\left|c\right(u)-c(v\left)\right|+D(u,v)\ge k+1$ for every two distinct vertices $u$ and $v$ of $G$. The value ${\chi }_m^k\left(c\right)$ of a $k$-metric coloring $c$ is the maximum color assigned by $c$ to a vertex of $G$ and the $k$-metric chromatic number ${\chi }_m^k\left(G\right)$ of $G$ is the minimum value of a $k$-metric coloring of $G$. For every...

Suppose that G is a simple, vertex-labeled graph and that S is a multiset. Then if there exists a one-to-one mapping between the elements of S and the vertices of G, such that edges in G exist if and only if the absolute difference of the corresponding vertex labels exist in S, then G is an autograph, and S is a signature for G. While it is known that many common families of graphs are autographs, and that infinitely many graphs are not autographs, a non-autograph has never been exhibited. In this...

A d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph ${⁺}_d\left(S\right)=(V,)$, where V = S and $=v₁,...,v_d:\left(i\ne j\Rightarrow v_i\ne v_j\right)\wedge {\sum }_{i=1}^d{v}_i\in S$. For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $w₁,...,w_{\sigma }\notin V$ such that $\cup w₁,...,w_{\sigma }$ is a sum hypergraph. In this paper, we prove $\sigma {(}_{n₁,...,n_d}^d)=1+{\sum }_{i=1}^d(n_i-1)+min0,\lceil 1/2({\sum }_{i=1}^{d-1}(n_i-1)-n_d)\rceil$, where ${}_{n₁,...,n_d}^d$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

The focus of this article is on three of the author's open conjectures. The article itself surveys results relating to the conjectures and shows where the conjectures are known to hold.