The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood $N_G\left[e\right]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and of all edges having a common end vertex with $e$. Let $f$ be a mapping of the edge set $E\left(G\right)$ of $G$ into the set $\{-1,1\}$. If ${\sum }_{x\in N\left[e\right]}f\left(x\right)\ge 1$ for each $e\in E\left(G\right)$, then $f$ is called a signed edge dominating function on $G$. The minimum of the values ${\sum }_{x\in E\left(G\right)}f\left(x\right)$, taken over all signed edge dominating function $f$ on $G$, is called the signed edge domination number...

For any vertex v and any edge e in a non-trivial connected graph G, the distance sum d(v) of v is $d\left(v\right)={\sum }_{u\in V}d(v,u)$, the vertex-to-edge distance sum d₁(v) of v is $d₁\left(v\right)={\sum }_{e\in E}d(v,e)$, the edge-to-vertex distance sum d₂(e) of e is $d₂\left(e\right)={\sum }_{v\in V}d(e,v)$ and the edge-to-edge distance sum d₃(e) of e is $d₃\left(e\right)={\sum }_{f\in E}d(e,f)$. The set M(G) of all vertices v for which d(v) is minimum is the median of G; the set M₁(G) of all vertices v for which d₁(v) is minimum is the vertex-to-edge median of G; the set M₂(G) of all edges e for which d₂(e) is minimum is the edge-to-vertex...

The open neighborhood $N_G\left(e\right)$ of an edge $e$ in a graph $G$ is the set consisting of all edges having a common end-vertex with $e$. Let $f$ be a function on $E\left(G\right)$, the edge set of $G$, into the set $\{-1,1\}$. If ${\sum }_{x\in N_G\left(e\right)}f\left(x\right)\ge 1$ for each $e\in E\left(G\right)$, then $f$ is called a signed edge total dominating function of $G$. The minimum of the values ${\sum }_{e\in E\left(G\right)}f\left(e\right)$, taken over all signed edge total dominating function $f$ of $G$, is called the signed edge total domination number of $G$ and is denoted by ${\gamma }_{st}^{\text{'}}\left(G\right)$. Obviously, ${\gamma }_{st}^{\text{'}}\left(G\right)$ is defined only for graphs $G$ which have no connected...

We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ’ₖ(G). Let fₖ be defined by $fₖ\left(\Delta \right)=ma{x}_{G:\Delta \left(G\right)=\Delta }{\chi }^{\text{'}}ₖ\left(G\right)$. We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.

Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → -1,1 satisfying ${\sum }_{e\in E_G\left(v\right)}x\left(e\right)\le 1$ for every v ∈ V(G), where $E_G\left(v\right)=uv\in E\left(G\right)\left|u\in V\right(G)$. The maximum of the values of ${\sum }_{e\in E\left(G\right)}x\left(e\right)$, taken over all signed matchings x, is called the signed matching number and is denoted by β’₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β’₁(G) for...

For an ordered $k$-decomposition $𝒟=\{G_1,G_2,...,G_k\}$ of a connected graph $G$ and an edge $e$ of $G$, the $𝒟$-code of $e$ is the $k$-tuple $c_{𝒟}\left(e\right)$ = ($d(e,G_1),$ $d(e,G_2),$ $...,$ $d(e,G_k)$), where $d(e,G_i)$ is the distance from $e$ to $G_i$. A decomposition $𝒟$ is resolving if every two distinct edges of $G$ have distinct $𝒟$-codes. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension ${dim}_{\text{d}}\left(G\right)$. A resolving decomposition $𝒟$ of $G$ is connected if each $G_i$ is connected for $1\le i\le k$. The minimum $k$ for which $G$...