A snark is a simple, cyclically \(4\)-edge connected, cubic graph with girth at least \(5\) and chromatic index \(4\). We give a complete list of all snarks of order less than \(30\). Motivated by the long standing discussion on trivial snarks (i.e. snarks which are reducible), we also give a brief survey on different reduction methods for snarks. For all these reductions we give the complete numbers of irreducible snarks of order less than \(30\) and the number of nonisomorphic \(3\)-critical subgraphs of these graphs. The results are obtained with the aid of a computer.

We give short proofs of theorems of Nash-Williams (on edge-partitioning a graph into acyclic subgraphs) and of Tutte (on edge-partitioning a graph into connected subgraphs). We also show that each theorem can be easily derived from the other.

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.