A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.

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.

In the first part of this paper we give necessary and sufficient conditions for some special classes of digraphs to have a (k,l)-kernel. One of them is the duplication of a set of vertices in a digraph. This duplication come into being as the generalization of the duplication of a vertex in a graph (see [4]). Another one is the D-join of a digraph D and a sequence α of nonempty pairwise disjoint digraphs. In the second part we prove theorems, which give necessary and sufficient conditions for special...

In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.

The concept of (k,l)-kernels of digraphs was introduced in [2]. Next, H. Galeana-Sanchez [4] proved a sufficient condition for a digraph to have a (k,l)-kernel. The result generalizes the well-known theorem of P. Duchet and it is formulated in terms of symmetric pairs of arcs. Our aim is to give necessary and sufficient conditions for digraphs without symmetric pairs of arcs to have a (k,l)-kernel. We restrict our attention to special superdigraphs of digraphs Pₘ and Cₘ.

For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G such that G...

Let $G$ be an undirected connected graph with $n$, $n\ge 3$, vertices and $m$ edges with Laplacian eigenvalues ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_{n-1}>{\mu }_n=0$. Denote by ${\mu }_I={\mu }_{r_1}+{\mu }_{r_2}+\cdots +{\mu }_{r_k}$, $1\le k\le n-2$, $1\le r_1<r_2<\cdots <r_k\le n-1$, the sum of $k$ arbitrary Laplacian eigenvalues, with ${\mu }_{I_1}={\mu }_1+{\mu }_2+\cdots +{\mu }_k$ and ${\mu }_{I_n}={\mu }_{n-k}+\cdots +{\mu }_{n-1}$. Lower bounds of graph invariants ${\mu }_{I_1}-{\mu }_{I_n}$ and ${\mu }_{I_1}/{\mu }_{I_n}$ are obtained. Some known inequalities follow as a special case.

S.M. Lee proposed the conjecture: for any n > 1 and any permutation f in S(n), the permutation graph P(Pₙ,f) is graceful. For any integer n > 1 and permutation f in S(n), we discuss the gracefulness of the permutation graph P(Pₙ,f) if $f={\prod }_{k=0}^{l-1}(m+2k,m+2k+1)$, and ${\prod }_{k=0}^{l-1}(m+4k,m+4k+2)(m+4k+1,m+4k+3)$ for any positive integers m and l.

In a manner analogous to a commutative ring, the L-ideal-based L-zero-divisor graph of a commutative ring R can be defined as the undirected graph Γ(μ) for some L-ideal μ of R. The basic properties and possible structures of the graph Γ(μ) are studied.

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1,3}$ and $K_{1,4}$ and a light 4-path P₄. The results obtained for $K_{1,3}$ and P₄ are best possible.

A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the...