An \(H\)-transformation on a simple \(3\)-connected cubic planar graph \(G\) is the dual operation of flip flop on the triangulation \(G^*\) of the plane, where \(G^*\) denotes the dual graph of \(G\). We determine the seven \(3\)-connected cubic planar graphs whose \(H\)-transformations are uniquely determined up to isomorphism.

Conditions are given for decomposing \(K_{m,n}\) into edge-disjoint copies of a bipartite graph \(G\) by translating its vertices in the bipartition of the vertices of \(K_{m,n}\). A construction of the bipartite adjacency matrix of the \(d\)-cube \(Q_d\) is given leading to a convenient \(\alpha\)-valuation and a proof that \(K_{d2^{d-2},d2^{d-1}}\) can be decomposed into copies of \(Q_d\) for \(d > 1\).

Let \(G\) be a connected graph of order \(n\) and let \(k\) be a positive integer with \(kn\) even and \(n \geq 8k^2 + 12k + 6\). We show that if \(\delta(G) \geq k\) and \(\max\{d(u), d(v)\} \geq n/2\) for each pair of vertices \(u,v\) at distance two, then \(G\) has a \(k\)-factor. Thereby a conjecture of Nishimura is answered in the affirmative.

A graph \(G = (V, E)\) is called \(E\)-cordial if it is possible to label the edges with the numbers from the set \(N = \{0,1\}\) and the induced vertex labels \(f(v)\) are computed by \(f(v) = \sum_{\forall u} f(u,v) \pmod{2}\), where \(v \in V\) and \(\{u,v\} \in E\), so that the conditions \( |v_f(0)| – |v_f(1)| \leq 1\) and \(\big| |e_f(0)| – |e_f(1)| \leq 1\) are satisfied, where \(|v_f(i)|\) and \(|e_f(i)|\), \(i = 0,1\), denote the number of vertices and edges labeled with \(0\)’s and \(1\)’s, respectively. The graph \(G\) is called \(E\)-cordial if it admits an \(E\)-cordial labeling. In this paper, we investigate \(E\)-cordiality of several families of graphs, such as complete bipartite graphs, complete graphs, wheels, etc.

Suppose \(G\) and \(G’\) are graphs on the same vertex set \(V\) such that for each \(v \in V\) there is an isomorphism \(\theta_x\) of \(G-v\) to \(G’-v\). We prove in this paper that if there is a vertex \(x \in V\) and an automorphism \(\alpha\) of \(G-x\) such that \(\theta_x\) agrees with \(\alpha\) on all except for at most three vertices of \(V-x\), then \(G\) is isomorphic to \(G’\). As a corollary we prove that if a graph \(G\) has a vertex which is contained in at most three bad pairs, then \(G\) is reconstructible. Here a pair of vertices \(x,y\) of a graph \(G\) is called a bad pair if there exist \(u,v \in V(G)\) such that \(\{u,v\} \neq \{x,y\}\) and \(G-\{x,y\}\) is isomorphic to \(G-\{u,v\}\).

A \(\{0,1\}\)-matrix \(M\) is tree graphic if there exists a tree \(T\) such that the edges of \(T\) are indexed on the rows of \(M\) and the columns are the incidence vectors of the edge sets of paths of \(T\). Analogously, \(M\) is ditree graphic if there exists a ditree \(T\) such that the directed edges of \(T\) are indexed on the rows of \(M\) and the columns are the incidence vectors of the directed-edge sets of dipaths of \(T\). In this paper, a simple proof of an excluded-minor characterization of the class of tree-graphic matrices that are ditree-graphic is given. Then, using the same proof technique, a characterization of a “special” class of tree-graphic matrices (which are contained in the class of consecutive \(1\)’s matrices) is stated and proved.

One of the fundamental results concerning cycles in graphs is due to Ore:
If \(G\) is a graph of order \(n \geq 3\) such that \(d(x) + d(y) \geq n\) for every pair of nonadjacent vertices \(x, y \in V(G)\), then \(G\) is hamiltonian.
We generalize this result using neighborhood unions of \(k\) independent vertices for any fixed integer \(k \geq 1\). That is, for \(A \subseteq V(G)\), let \(N(A) = \cup_{a \in A} N(a),\)
where \(N(a) = \{b : ab \in E(G)\}\) is the neighborhood of \(a\). In particular, we show:
In a \(4(k-1)\)-connected graph \(G\) of order \(n \geq 3\), if \(|N(S)|+|N(T)| \geq n\) for every two disjoint independent vertex sets \(S\) and \(T\) of \(k\) vertices, then \(G\) is hamiltonian.
A similar result for hamiltonian connected graphs is obtained too.

The imbalance of edge \((x,y) = | \deg(x) – \deg(y) |\).The sum of all edge imbalances in a graph is called its irregularity.
We determine the maximum irregularity of various classes of graphs.For example, the irregularity of an arbitrary graph with \(n\) vertices is less than \(\frac{4n^3}{27}\), and this bound is tight.

In this paper we show that simplicial graphs, in which every vertex belongs to exactly one simplex, characterize graphs satisfying equality in some graph invariants concerning independence, clique covering, domination or distance.

The plane in the title is investigated from the combinatorial point of view.Its Baer subplanes are classified and their distribution is studied.Properties of the Fano subplanes are shown.Blocking sets of Rédei type are constructed.
Finally, hyperovals and complete \(14\)-arcs are considered and classified.

A graph \(G\) is \(H\)-decomposable if \(G\) can be decomposed into graphs, each of which is isomorphic to \(H\).
A graph \(G\) without isolated vertices is a least common multiple of two graphs \(G_1\) and \(G_2\) if \(G\) is a graph of minimum size such that \(G\) is both \(G_1\)-decomposable and \(G_2\)-decomposable.
It is shown that two graphs can have an arbitrarily large number of least common multiples.
All graphs \(G\) for which \(G\) and \(P_3\) (and \(G\) and \(2K_2\)) have a unique least common multiple are characterized.
It is also shown that two stars \(K_{1,r}\) and \(K_{1,s}\) have a unique least common multiple if and only if \(r\) and \(s\) are not relatively prime.

A Restricted Resolvable Design \(R_rRP(p, k)\) is a resolvable design on \(p\) points with block sizes \(r\) and \(r+1\) in which each point appears \(\alpha\) times. An \(RRP\) is called uniform if all resolution classes consist of the blocks of the same size.
We show that a uniform \(R_3RP(p,\frac{p}{2} -2)\) exists for all \(p \equiv 12 \mod 24, p \neq 12\) except possibly when \(p = 84\) or \(156\).
We also show that if \(g \equiv 3 \mod 6, g \notin \{3, 21, 39\}\) and \(p = 4g \mod 8g\) then there exists an \(R_3RP(p, \frac{p}{2}-(r+1))\) for all

1. \(r \leq \frac{p-4g}{8g}\) if \(\frac{p}{4g}\) is a prime power congruent to \(1 \mod 6\);
2. \(r \leq \frac{p}{4gq}\) where \(q\) is the smallest proper factor of \(\frac{p}{4g}\) if \(\frac{p}{4g}\) is composite and there exists an \(RT(9, \frac{p}{4gp})\).

The core of a graph was defined by Morgan and Slater [MS80] as a path in the graph minimizing the sum of the distance of all vertices of the graph from the path. A linear algorithm to find the core of a tree has been given in [MS80]. For the general graph the problem can be shown to be NP-hard using a reduction from the Hamiltonian path problem.
A graph with no chordless cycle of length exceeding three is called a chordal graph. Every chordal graph is the intersection graph of a family of subtrees of a tree. The intersection graph of a family of undirected paths of a tree is called a UV graph. The intersection graph of an edge disjoint family of paths of a tree is called a CV graph [AAPX91]. We have characterised that the CV graphs are nothing but block graphs. CV graphs form a proper subclass of UV graphs which in turn form a proper subclass of chordal graphs.
In this paper, we present an \( {O}(ne)\) algorithm to find the core of a CV graph, where \(n\) is the number of vertices and \(e\) is the number of edges.

The worst-case time-complexity of Read’s edge-addition/contraction algorithm for computing the chromatic polynomial of an \(n\)-vertex graph is shown to be \({O}(n^2B(n))\), where \(B(n)\) is the \(n\)th Bell number, which grows faster than \(c^n\) for any \(c\) but slower than \(n!\). The factor \(n^2\) can be reduced to \(n\), and the space-complexity from \({O}(n^3)\) to \({O}(n^2)\), by storing in arrays the information needed to reverse each transformation made on the graph.

This paper provides an expository account, from a design-theoretic point of view, of the important result of Ryser that covering of the complete graph \(K_v\) a total of \(\lambda\) times by \(v\) complete subgraphs can only be done in a very limited number of ways.

We give an exponential lower bound for the maximum number of chords in a cycle of a graph \(G\) in terms of the minimum degree of \(G\) and the girth of \(G\). We also give regular graphs having no small cycles where the maximum number of chords possible in any cycle of the graph is approximately the fourth power of our lower bound. An immediate consequence is a recent result of Ali and Staton.

The edge-integrity of a graph \(G\) is given by the minimum of \(|S|+m(G-S)\) taken over all \(S \subseteq E(G)\), where \(m(G-S)\) denotes the maximum order of a component of \(G-S\). An honest graph is one with maximum edge-integrity (viz. its order). In this paper, lower and upper bounds on the edge-integrity of a graph with given order and diameter are investigated. For example, it is shown that the diameter of an honest graph on \(n\) vertices is at most \(\sqrt{8n}-3\), and this is sharp. Also, a lower bound for the edge-integrity of a graph in terms of its eigenvalues is established. This is used to show that for \(d\) sufficiently large, almost all \(d\)-regular graphs are honest.

An element \(e\) of a matroid \(M\) is called non-binary when \(M\backslash e\) and \(M/e\) are both non-binary matroids. Oxley in \({6}\) gave a characterization of the \(3\)-connected non-binary matroids without non-binary elements. In {4}, we constructed all the \(3\)-connected matroids having exactly \(1\), \(2\) or \(3\) non-binary elements. In this paper, we will give a characterization of the \(3\)-connected matroids having exactly four non-binary elements.

In \([2, 3]\), the authors dealt with the problem of determining the set \(\Gamma(G)\) of all \((a, d)\)-antimagic graphs, \(a, d \in \mathbb{N}\), where the concept of an \((a, d)\)-antimagic graph is a variation of the concept of an antimagic graph given in [4]. A connected graph \(G = (V, E) \in \Gamma=\) set of all finite undirected graphs without loops and multiple edges on \(n = |V| \geq 3\) vertices and \(m = |E| \geq 2\) edges is said to be \((a, d)\)-antimagic iff its edges can be assigned mutually distinct nonnegative integers from \(\{1, 2, \ldots, m\}\) so that the values of the vertices obtained as the sums of the numbers assigned to the edges incident to them can be arranged in the arithmetic progression \(a, a + d, \ldots, a + (n – 1)d\). In [2], the authors obtained some interesting general results on \((a, d)\)-antimagic graphs from \(\Gamma(G)\) by applying the theory of linear Diophantine equations and other number theoretical topics. Applying these general results to wheels \(W_{g , b} = 1 \ast C_{g + b}, g \geq 3, b \geq 1, C_{g + b} =\) cycle of order \(g + b\), and parachutes \(P_{g, b}\) as the spanning subgraph of \(W_{g+b}\) arising from \(W_{g+b}\) by removing \(b\) successive spokes of \(W_{g+b}\), we succeeded in proving that every wheel \(W_{g+b}\) cannot be \((a, d)\)-antimagic and, for every \(g \geq 3\) or \(g \geq 4\), there are the five integers \(b_1 = 2g^2 – 3g – 1, b_2 = g^2 – 2g – 1, b_3 = g – 1, b_4 = g – 3\) and \(b_5 = \frac{1}{2}(g^2 – 3g – 2)\) with the property that the corresponding parachute \(P_{g, b_i}, i = 1, 2, \ldots, 5\), can be \((a, d)\)-antimagic. If \(\Gamma_i(P)\) denotes the set \(\Gamma_i(P)= \{P_{g, b_i} \in \Gamma(P) \mid g \geq 3\}, i = 1, 2, \ldots, 5\), the main result in [2] says that \(\Gamma_3(P) = \{P_{3, 2}, P_{4, 3},\ldots, P_{8,7}, P_{10,9}, P_{11, 10}\}\) and \(\Gamma_4(P) = \{P_{4, 1}, P_{5, 2}, \ldots, P_{10, 7}\}\). Concerning \(\Gamma_1(P), \Gamma_2(P)\) and \(\Gamma_5(P)\) the authors conjecture that they are infinite. Here, we continue [2] and prove the conjecture given in [2] for \(\Gamma_1(P)\) and \(\Gamma_2(P)\). Instead of \(\Gamma(P)\) we prove the infiniteness of \(\Gamma'(P) = \{P_g,\frac{1}{3} (2g^2 – 5g – 3) \in \Gamma(P) \mid g \equiv 0(3) \text{ or } g \equiv 1(3)\}\). Furthermore, we succeed in showing the existence of integers \(b_{min} \in \{\frac{g^2 – 3g – 2}{2}, \frac{g^2 – 4g – 3}{3},\frac{g^2 – 5g – 4}{4}, \frac{2g^2 – 7g – 5}{5}, \}\) with respect to \(g \geq 26\) with the property that the parachute \(P_{g, b}\) is not \((a, d)\)-antimagic for each positive integer \(b \leq b_{min}\). The immediate consequence of this fact is that for every \(g \geq 26\) there are at most \(8\) different integers \(b \geq b_{min}\) such that the corresponding parachute \(P_{g, b}\) could be \((a, d)\)-antimagic.

Let \(\gamma(G)\) be the domination number of a graph \(G\). The bondage number \(b(G)\) of a nonempty graph \(G\) is the minimum cardinality among all sets of edges \(X\) for which \(\gamma(G – X) > \gamma(G)\).

In this paper we show that \(b(G) \leq \Delta(G)\) for any block graph \(G\), and we characterize all block graphs with \(b(G) = \Delta(G).\)

We report on difficulties in applying traditional clustering procedures to discrete data. We describe a graph theoretical approach in clustering binary vectors where the number of clusters is not given in advance. New clustering procedures are combined from several algorithms and heuristics from graph theory.