A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σv∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ⊆ V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The...

In this paper, we study the signed total domination number in graphs and present new sharp lower and upper bounds for this parameter. For example by making use of the classic theorem of Turán [8], we present a sharp lower bound on Kr+1-free graphs for r ≥ 2. Applying the concept of total limited packing we bound the signed total domination number of G with δ(G) ≥ 3 from above by [...] . Also, we prove that γst(T) ≤ n − 2(s − s′) for any tree T of order n, with s support vertices and s′ support vertices...

A maximum matching of a graph $G$ is a matching of $G$ with the largest number of edges. The matching number of a graph $G$, denoted by ${\alpha }^{\text{'}}\left(G\right)$, is the number of edges in a maximum matching of $G$. In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture is true for...

So far, the smallest complete bipartite graph which was known to have a cyclic decomposition into cubes $Q_d$ of a given dimension d was $K_{d{2}^{d-1},d{2}^{d-2}}$. We improve this result and show that also $K_{d{2}^{d-2},d{2}^{d-2}}$ allows a cyclic decomposition into $Q_d$. We also present a cyclic factorization of $K_{8,8}$ into Q₄.

A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced by X has maximum degree one. The 1-dependent Ramsey number t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ has a 1-dependent set of size l or the subgraph R has a 1-dependent set of size m. The 2-edge colouring (R,B) is a t₁(l,m) Ramsey colouring of Kₙ if B (R, respectively) does not contain a 1-dependent set of size l (m, respectively); in this...

Let $GP(n,k)$ be a generalized Petersen graph with $(n,k)=1$, $n>k\ge 4.$ Then every pair of parallel edges of $GP(n,k)$ is contained in a 1-factor of $GP(n,k)$. This partially answers a question posed by Larry Cammack and Gerald Schrag [Problem 101, Discrete Math. 73(3), 1989, 311-312].

We consider cubic graphs formed with k ≥ 2 disjoint claws $C_i{K}_{1,3}$ (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of $C_i$ are joined to the three vertices of degree 1 of $C_{i-1}$ and joined to the three vertices of degree 1 of $C_{i+1}$. Denote by $t_i$ the vertex of degree 3 of $C_i$ and by T the set $t₁,t₂,...,t_{k-1}$. In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices ${\bigcup }_{i=0}^{i=k-1}V\left(C_i\right)\setminus T$ induce j cycles (note that the graphs...