In this paper we refine Whitney’s Theorem on \(k\)-connected graphs for \(k \geq 3\). In particular we show the following: Let \(G\) be a \(k\)-connected graph with \(k \geq 3\). For any two distinct vertices \(u\) and \(v\) of \(G\) there are \(k\) internally vertex disjoint paths \(P_1[u,v], P_2[u,v], \dots, P_k[u,v]\) such that \(G – V(P_i(u,v))\) is connected for \(i = 1, 2, \dots, k\), where \(P_i(u, v)\) denotes the internal vertices of the path \(P_i[u, v]\). Further one of the following properties holds:

1. \(G – V(P_i[u, v])\) is connected for \(i = 1, 2, 3\).
2. \(G – V(P_i[u, v])\) is connected for \(i = 1, 2\) and \(G – V(P_i[u, v])\) has exactly two connected components for \(i = 3, 4, \dots, k\).

In addition, some other properties will be proved.

Some results relating to the road-coloring conjecture of Alder, Goodwyn, and Weiss, which give rise to an \(O(n^2)\) algorithm to determine whether or not a given edge-coloring of a graph is a road-coloring, are noted. Probabilistic analysis is then used to show that, if the outdegree of every edge in an \(n\)-vertex digraph is \(\delta = \omega(\log n)\), a road-coloring for the graph exists. An equivalent re-statement of the conjecture is then given in terms of the cross-product of two graphs.

A graph \(G = (V, E)\) is a loop niche graph if there is a digraph \(D = (V, A)\)such that \(xy \in E\) iff there exists \(z \in V\) such that either \(xz\) and \(yz \in A\) or \(zx\) and \(zy \in A\). If \(D\) has no loops, \(G\) is a cyclic niche graph, and if \(D\) is acyclic, \(G\) is a niche graph. We give a characterization of triangle-free cyclic niche graphs, and apply this to classify grids.

Let \(\Phi(N)\) be the maximum number of simple polygons that can be drawn using as vertices a set \(V\) of \(N\) points in the plane. By counting the number of simple polygons of a particular configuration of \(V\), an improved lower bound for \(\Phi(N)\) is obtained. It is proved that \(\Phi(N)^\frac{1}{N}\) is asymptotically greater than \(3.6\).

A graph \(G\) is maximally non-hamiltonian \((MNH)\) if \(G\) is not hamiltonian but becomes hamiltonian after adding an arbitrary new edge. Bondy \([2]\) showed that the smallest size \((=\)number of edges) in a \(MNH\) graph of order \(n\) is at least \(\left\lceil\frac{3n}{2}\right\rceil\) for \(n \geq 7\). The fact that equality may hold for infinitely many \(n\) was suggested by Bollobas [1]. This was confirmed by Clark, Entringer, and Shapiro (see [5,6]) and by Xiaobui, Wenzhou, Chengxue, and Yuanscheng [8] who set the values of the size of smallest \(MNH\) graphs for all small remaining orders \(n\). An interesting question of Clark and Entringer [8] is whether for infinitely many \(n\) the smallest \(MNH\) graph of order \(n\) is not unique. A positive answer – the existence of two non-isomorphic smallest \(MNH\) graphs for infinitely many \(n\) follows from results in \([5], [4], [6]\), and \([8]\). But, there still exist infinitely many orders \(n\) for which only one smallest \(MNH\) graph of order \(n\) is known.

We prove that for all \(n \geq 88\) there are at least \(\tau(n) > 3\) smallest \(MNH\) graphs of order \(n\), where \(\lim_{n\to\infty} \tau(n) = \infty\). Thus, there are only finitely many orders \(n\) for which the smallest \(MNH\) graph is unique.

We deal with \((a, d)\)-antimagic labelings of the prisms.
A connected graph \(G = (V, E)\) is said to be \((a, d)\)-antimagic if there exist positive integers \(a, d\) and a bijection \(f: E \to \{1, 2, \ldots, |E|\}\) such that the induced mapping \(g_f: V \to {N}\), defined by \(g_f(v) = \sum \{f(u, v): (u, v) \in E(G)\}\), is injective and \(g_f(V) = \{a, a + d, \ldots, a + (|V| – 1)d\}\).

We characterize \((a, d)\)-antimagic prisms with even cycles and we conjecture that prisms with odd cycles of length \(n\), \(n \geq 7\), are \((\frac{n+7}{2}, 4)\)-antimagic.

We establish some basic facts about sign-patterns of orthogonal matrices, and use these facts to characterize the sign-nonsingular matrices which are sign-patterns of orthogonal matrices.

In this paper, we give some properties of balanced labeling, prove that the graph \((m^2 + 1)C_4\) is balanced, and also solve the balanceness of snakes \(C_m(n)\).

In this note, we verify two conjectures of Catlin in [J.Graph Theory \(13 (1989)465-483\)] for graphs with at most \(11\) vertices. These are used to prove the following theorem, which improves prior results in \([10]\) and \([13]\):

Let \(G\) be a 3-edge-connected simple graph with order \(n\). If \(n\) is large and if for every edge \(uv \in E(G)\), \(d(u) + d(v) \geq \frac{n}{6} – 2\), then either \(G\) has a spanning eulerian subgraph or $G$ can be contracted to the Petersen graph.

Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(VNI(G)\), is defined as:

\(VNI(G) = \min_{|S|} {|S| + w(G/S)}\)

where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we evaluate the vertex-neighbor-integrity of the powers of cycles, and show that among the powers of the \(n\)-cycle, the maximum vertex-neighbor-integrity is \(\left\lceil{2}\sqrt{n}\right\rceil – 3\) and the minimum vertex-neighbor-integrity is \(\left\lceil\frac{n}{2\left\lfloor\frac{n}{2}\right\rfloor} + 1\right\rceil\).