A matching in a graph \(G\) is a set of independent edges and a maximal matching is a matching that is not properly contained in any other matching in \(G\). A maximum matching is a matching of maximum cardinality. The number of edges in a maximum matching is denoted by \(\beta_1(G)\); while the number of edges in a maximal matching of minimum cardinality is denoted by \(\beta^-_1(G)\). Several results concerning these parameters are established including a Nordhaus-Gaddum result for \(\beta^-_1(G)\). Finally, in order to compare the maximum matchings in a graph \(G\), a metric on the set of maximum matchings of \(G\) is defined and studied. Using this metric, we define a new graph \(M(G)\), called the matching graph of \(G\). Several graphs are shown to be matching graphs; however, it is shown that not all graphs are matching graphs.

In this paper we consider interval colourings — edge colourings of bipartite graphs in which the colours represented at each vertex form an interval of integers. These colourings, corresponding to certain types of timetables, are not always possible. In the present paper it is shown that if a bipartite graph with bipartition \((X,Y)\) has all vertices of \(X\) of the same degree \(d_X = 2\) and all vertices of \(Y\) of the same degree \(d_y\), then an interval colouring can always be established.

Let \(v\) and \(u\) be positive integers. It is shown in this paper that the necessary condition for the existence of a directed \(\mathrm{TD}(5,v)\)-\(\mathrm{TD}(5,u)\), namely \(v \geq 4u\), is also sufficient.

Initiated by a recent question of Erdhos, we give lower bounds on the size of a largest \(k\)-partite subgraph of a graph. Also, the corresponding problem for uniform hypergraphs is considered.

Let \(G = (V, E)\) be a graph and \(k \in \mathbb{Z}^+\) such that \(1 \leq k \leq |V|\). A \(k\)-subdominating function (KSF) to \(\{-1, 0, 1\}\) is a function \(f: V \to \{-1, 0, 1\}\) such that the closed neighborhood sum \(f(N[v]) \geq 1\) for at least \(k\) vertices of \(G\). The weight of a KSF \(f\) is \(f(V) = \sum_{v \in V} f(v)\). The \(k\)-subdomination number to \(\{-1, 0, 1\}\) of a graph \(G\), denoted by \(\gamma^{-101}_{k_s}(G)\), equals the minimum weight of a KSF of \(G\). In this paper, we characterize minimal KSF’s, calculate \(\gamma^{-101}_{k_s}(G)\) for an arbitrary path \(P_n\), and determine the least order of a connected graph \(G\) for which \(\gamma^{-101}_{k_s}(G)=-m\) for an arbitrary positive integer \(m\).

Let \(G\) be a simple graph of order \(n\) having a maximum matching \(M\). The deficiency \( def(G)\) of \(G\) is the number of vertices unsaturated by \(M\). In this paper, we find lower bounds for \(n\) when \( def(G)\) and the minimum degree (or maximum degree) of vertices are given. Further, for every \(n\) not less than the bound and of the same parity as \( def(G)\), there exists a graph \(G\) with the given deficiency and minimum (maximum) degree.

In this paper, we count the number of isomorphism classes of bipartite \(n\)-cyclic permutation graphs up to positive natural isomorphism and show that it is equal to the number of double cosets of the dihedral group \(D_n\) in the subgroup \(B_n\) of the symmetric group \(S_n\), consisting of parity-preserving or parity-reversing permutations.

Let \(\alpha(G)\) denote the independence number of a graph \(G\) and let \(G \times H\) be the direct product of graphs \(G\) and \(H\). Set \(\underline{\alpha}(G\times H) = \max\{\alpha(G) – |H|, \alpha(H) – |G|\}\). If \(G\) is a path or a cycle and \(H\) is a path or a cycle, then \(\alpha(G \times H) = \underline{\alpha}(G \times H)\). Moreover, this equality holds also in the case when \(G\) is a bipartite graph with a perfect matching and \(H\) is a traceable graph. However, for any graph \(G\) with at least one edge and for any \(i \in \mathbb{N}\), there is a graph \(H_c\) such that \(\alpha(G \times H ) > \underline{\alpha}(G \times H ) + i\).

Our main aim is to show that the Randi\’e weight of a connected graph of order \(n\) is at least \(\sqrt{n – 1}\). As shown by the stars, this bound is best possible.

New class \(\mathcal{GBG}_{\overrightarrow{k}}\), of generalized de Bruijn multigraphs of rank \({\overrightarrow{k}}\in{N}^m\), is introduced and briefly characterized. It is shown, among the others, that every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\) is connected, Eulerian and Hamiltonian. Moreover, it consists of the subgraphs which are isomorphic with the de Bruijn graphs of rank \(r=\sum_{i=1}^{m} (d_1,\dots,d_m)\in\{0.1\}^m\). Then, the subgraphs of every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\), called the \({\overrightarrow{k}}\)-factors, are distinguished.

An algorithm, with small time and space complexities, for the construction of the \({\overrightarrow{k}}\)-factors, in particular the Hamiltonian circuits, is given. At the very end, a few open problems are put forward.