We derive several new lower bounds on the size of ternary covering codes of lengths \(6\), \(7\) and \(8\) and with covering radii \(2\) or \(3\).

We show that every complete graph \(K_n\), with an edge-colouring without monochromatic triangles, has a properly coloured Hamiltonian path.

In this paper we prove some basic properties of the \(g\)-centroid of a graph defined through \(g\)-convexity. We also prove that finding the \(g\)-centroid of a graph is NP-hard by reducing the problem of finding the maximum clique size of \(G\) to the \(g\)-centroidal problem. We give an \(O(n^2)\) algorithm for finding the \(g\)-centroid for maximal outer planar graphs, an \(O(m + n\log n)\) time algorithm for split graphs and an \(O(m^2)\) algorithm for ptolemaic graphs. For split graphs and ptolemaic graphs we show that the \(g\)-centroid is in fact a complete subgraph.

In this paper, we show that if \(G\) is a connected \(SN2\)-locally connected claw-free graph with \(\delta(G) \geq 3\), which does not contain an induced subgraph \(H\) isomorphic to either \(G_1\) or \(G_2\) such that \(N_1(x,G)\) of every vertex \(x\) of degree \(4\) in \(H\) is disconnected, then every \(N_2\)-locally connected vertex of \(G\) is contained in a cycle of all possible lengths and so \(G\) is pancyclic. Moreover, \(G\) is vertex pancyclic if \(G\) is \(N_2\)-locally connected.

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.