Let $G$ be a simple graph. A function $f$ from the set of orientations of $G$ to the set of non-negative integers is called a continuous function on orientations of $G$ if, for any two orientations $O_1$ and $O_2$ of $G$, $|f\left(O_1\right)-f\left(O_2\right)|\le 1$ whenever $O_1$ and $O_2$ differ in the orientation of exactly one edge of $G$. We show that any continuous function on orientations of a simple graph $G$ has the interpolation property as follows: If there are two orientations $O_1$ and $O_2$ of $G$ with $f\left(O_1\right)=p$ and $f\left(O_2\right)=q$, where $p<q$, then for any integer $k$ such that...

The domination subdivision number $s{d}_{\gamma }\left(G\right)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

A graph $G$ is a $\{d,d+k\}$-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\{d,d+k\}$-graph of order $n$ without a matching $M$ of size $2\left|M\right|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta$ for $k\ge d(p+3)+p+4+\eta$, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$,...

The irregularity of a graph $G=(V,E)$ is defined as the sum of imbalances $|d_u-d_v|$ over all edges $uv\in E$, where $d_u$ denotes the degree of the vertex $u$ in $G$. This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ($1\le p\le n-1$), and characterize the corresponding extremal graphs.

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V=v₀,v₁,...,v_{n-1}$, $E₁=v₀v₁,...,v₀v_{n-3},v_{n-4}{v}_{n-2},v_{n-3}{v}_{n-1}$ and $E₂=v₀v₁,...,v₀v_{n-3},v_{n-3}{v}_{n-2},v_{n-3}{v}_{n-1}$. For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r(Tₘ,T{ₙ}^i)$, where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$, denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $\mathrm{pc}\left(G\right)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$-coloring for a connected bipartite graph $G$ having $\delta \left(G\right)\ge 2$ and a dominating...

We study edge-sum distinguishing labeling, a type of labeling recently introduced by Z. Tuza (2017) in context of labeling games. An ESD labeling of an $n$-vertex graph $G$ is an injective mapping of integers $1$ to $l$ to its vertices such that for every edge, the sum of the integers on its endpoints is unique. If $l$ equals to $n$, we speak about a canonical ESD labeling. We focus primarily on structural properties of this labeling and show for several classes of graphs if they have or do not...