Springer Science and Business Media LLC

Let D =  (V, A) be a simple finite digraph, and let $${\pi(D)}$$ , the panchromatic number of D, be the maximum number of colours k such that for each (effective, or onto) colouring of its arcs $${\varsigma : A \to [k]}$$ a monochromatic path kernel N ⊂ V, as introduced in Galeana-Sánchez (Discrete Math 184: 87–99, 1998), exists. It is not hard to see that D has a kernel—in the sense of Von Neumann and Morgenstern (Theory of games and economic behaviour. Princeton University Press, Princeton, 1944)—if and only if $${\pi(D) = |A|}$$ . In this note this invariant is introduced and some of its structural bounds are studied. For example, the celebrated theorem of Sands et al. (J Comb Theory Ser 33: 271–275, 1982), in terms of this invariant, settles that $${\pi(D) \geq 2}$$ . It will be proved that $$\pi(D) < |A| \iff \pi(D) < \min \left\{2\sqrt{\chi(D)}, \chi(L(D)), \theta(D) + \max {\text d}_c(K_i) + 1\right\},$$ where $${\chi(\cdot)}$$ denotes the chromatic number, $${L(\cdot)}$$ denotes the line digraph, $${\theta(\cdot)}$$ denotes the minimum partition into complete graphs of the underlying graph and $${\text{d}_c(\cdot)}$$ denotes the dichromatic number. We also introduce the notion of a panchromatic digraph which is a digraph D such that for every k ≤  |A| and every k-colouring of its arcs, it has a monochromatic path kernel. Some classes of panchromatic digraphs are further characterised.

For a simple graph G, the graph’s spread s(G) is defined as the difference between the largest eigenvalue and the least eigenvalue of the graph’s adjacency matrix, i.e. $${s(G)=\rho(G)-\lambda(G)}$$ . A connected graph G is a cactus if any two of its cycles have at most one common vertex. If all cycles of the cactus G have exactly one common vertex then it is called a bundle. Let $${{\mathcal C}(n,k)}$$ denote the class of cacti with n vertices and k cycles. In this paper, we determine a unique cactus whose spread is maximal among the cacti with n vertices and k cycles. We prove that the obtained graph is a bundle of a special form. Within the class $${{\mathcal C}(n,k)}$$ we also present a unique cactus whose least eigenvalue is minimal (Petrović et al. in Linear Algebra Appl 435:2357–2364, 2011) and show that these two graphs are the same, except for a few cases in which n is small.

If I is a set ofk − 1 arcs in ak-connected tournamentT, thenT − I has a Hamiltonian dicycle.

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least $${\frac{1}{2}|G|}$$ vertices of degree 5.

For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6t − 6, we completely characterize such graphs.

We enumerate labelled threshold graphs by the number of vertices, the number of isolated vertices, and the number of distinct vertex-degrees and we give the exact asymptotics for the number of labelled threshold graphs withn vertices. We obtain the appropriate generating function and point out a combinatorial interpretation relating its coefficients to the Stirling numbers of the second kind. We use these results to derive a new proof of a theorem of Frobenius expressing the Eulerian polynomials in terms of the Stirling numbers.

In this paper we give a new Hadamard matrix of order 24 and its properties. This matrix must be appear in [11]. By this paper and Ito-Leon-Longyear [3] the classification of Hadamard matrices of order 24 is completed.

Let G be a finite abelian group viewed a $${\mathbb {Z}}$$ -module and let $${\mathcal {G}} = (V, E)$$ be a simple graph. In this paper, we consider a graph $$\Gamma (G)$$ called as a group-annihilator graph. The vertices of $$\Gamma (G)$$ are all elements of G and two distinct vertices x and y are adjacent in $$\Gamma (G)$$ if and only if $$[x : G][y : G]G = \{0\}$$ , where $$x, y\in G$$ and $$[x : G] = \{r\in {\mathbb {Z}} : rG \subseteq {\mathbb {Z}}x\}$$ is an ideal of a ring $${\mathbb {Z}}$$ . We discuss in detail the graph structure realised by a group G. Moreover, we study the creation sequence, hyperenergeticity and hypoenergeticity of group-annihilator graphs. Finally, we conclude the paper with a discussion on Laplacian eigen values of the group-annihilator graph. We show that the Laplacian eigen values are representatives of orbits of the group action: $$Aut(\Gamma (G)) \times G \rightarrow G$$ .