We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is s‐chromatic if it is colorable in s colors and any coloring of it uses at least s colors. The forcing chromatic number $F_{\chi}(G)$ of an s‐chromatic graph G is the smallest number of vertices which must be colored so that, with the restriction that s colors are used, every remaining vertex has its color determined uniquely. We estimate the computational complexity of $\force G$ relating it to the complexity class US introduced by Blass and Gurevich [Inform. Control, 55 (1982), pp. 80–88]. We prove that recognizing whether $F_{\chi}(G)\le2$ is US‐hard with respect to polynomial‐time many‐one reductions. Moreover, this problem is coNP‐hard even under the promises that $F_{\chi}(G)\le3$ and G is 3‐chromatic. On the other hand, recognizing whether $F_{\chi}(G)\le k$, for each constant k, is reducible to a problem in US via a disjunctive truth‐table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph.

Abstract For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u − v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u, v) for u, v ∈ S. The geodetic number g(G) is the minimum cardinality among the subsets S of V(G) with I(S) = V(G). It is shown that if G is a graph of order n and diameter d then g(G) ≤ n − d + 1 and this bound is sharp. For positive integers r, d, and k ≥ 2 with r ≤ d ≤ 2r, there exists a connected graph G of radius r, diameter d, and g(G) = k. Also, for integers n, d, and k with 2 ≤ d < n, 2 ≤ k < n, and n − d − k + 1 ≥ 0, there exists a graph G of order n, diameter d, and g(G) = k. It is shown, for every nontrivial connected graph G, that g(G) ≤ g(G × K2). A sufficient condition for the equality of g(G) and g(G × K2) is presented. A graph F is a minimum geodetic subgraph if there exists a graph G containing F as an induced subgraph such that V(F) is a minimum geodetic set for G. Minimum geodetic subgraphs are characterized. © 2002 John Wiley & Sons, Inc.

A graph G* is a k-node fault-tolerant supergraph of a graph G, denoted k-NFT (G), if every graph obtained by removing k nodes from G* contains G. A k-NFT (G) graph G* is said to be optimal if it contains n + k nodes, where n is the number of nodes of G and G* has the minimum number of edges among all (n + k)-node k-NFT supergraphs of G. We survey prior results on the design of optimal k-NFT supergraphs of various useful forms of G; this work covers cycles and various types of trees. We also introduce the concept of exact node fault tolerance, which requires that every graph obtained by removing k nodes from G* be isomorphic to G, and explore its basic properties. We conclude with a discussion of some unsolved and partially solved problems. © 1996 John Wiley & Sons, Inc.

Abstract A graph or multigraph G* is k‐edge fault‐tolerant with respect to a graph G, denoted k‐EFT(G), if every graph obtained by removing any k edges from G* contains G. We observe that for k sufficiently large a k‐EFT(G) graph must be a multigraph, and we present some basic conditions that such multigraphs must meet. We then study the problem of constructing k‐EFT(G) graphs that are optimal in that they contain the minimum number of edges among all k‐EFT(G) graphs. Families of optimal k‐EFT(G) graphs, where G is the n‐node path or cycle, are presented for all k and n. We also give an optimal 1‐EFT design for the n‐dimensional hypercube. © 1993 by John Wiley & Sons, Inc.

In this semi-expository note, we first recall that every boolean function f of n variables is determined uniquely by a certain subset S of the nodes of the hypercube Q". We then propose the subgraph of Qn induced by S as a realization of f, and call it the graph of a boolean function. We observe that boolean functions of the same type always have the same graph, but the converse does not hold. We conclude with the open question which suggests itself from a confrontation of the disjunctive and conjunctive normal forms of a boolean function.

Abstract A graph G is called invertible if its adjacency matrix A has an inverse which is the adjacency matrix of some graph H. All such graphs were shown by Harary and Minc to have the form nK2. We now introduce signed invertible (or briefly s‐invertible) graphs G as those whose inverse H is a signed graph. We identify two infinite classes of s‐invertible graphs: the paths P2n of even order, and the corona of any graph with K1. We then characterize s‐invertible trees.

Abstract For a noncomplete graph G , the traditional definition of its connectivity is the minimum number of points whose removal results in a disconnected subgraph with components H 1 ,…, H k . The conditional connectivity of G with respect to some graph‐theoretic property P is the smallest cardinality of a set S of points, if any, such that every component H i of the disconnected graph G ‐ S has property P. A survey of promising properties P is presented. Questions for various P ‐connectivities are listed in analogy with known results on connectivity and line‐connectivity.

Abstract We propose a generalization of signed graphs, called group graphs. These are graphs regarded as symmetric digraphs with a group element s ( u, v ) called the signing associated with each arc ( u, v ) such that s ( u, v ) s ( v, u ) = 1. A group graph is balanced if the product s ( v 1 , v 2 ) s ( v 2 , v 3 ) … s ( u m , v 1 ) = 1 for each cycle v 1 , v 2 ,…, v m , v 1 in the graph. Let G denote the graph, F the group (not necessarily commutative), and s the signing. Then the group graph is denoted by ( G, F, s ). Given a group graph ( G, F, s ), which need not be balanced, we define the deletion index δ( G, F, s ) as the minimum cardinality of a deletion set , which is a subset of lines whose deletion results in a balanced group graph. Similarly we define the alteration index γ( G, F, s ) as the minimum cardinality of a alteration set , which is a set of lines { u, v } in the graph the values s ( u, v ) and s ( v, u ) of which can be changed so that the new group graph is balanced. When F is the group of order 2, we obtain a signed graph. Generalizing results known for signed graphs, we prove that minimal deletion sets are minimal change sets, which implies the equality δ( G, F, s ) = γ( G, F, s ) for all G, F , and s. We also prove the in‐equality δ ( G, F, s ) ≤ ( n ‐ 1) q/n , where q is the number of lines in the graph G and n is the order of the group F. We conclude by studying δ for signed complete bigraphs K n,n when the signing is determined from a Hadamard matrix.

Abstract The connectivity contribution or cohesiveness of a point v of graph G is defined as the difference k(G) ‐ k(G ‐ v) where kappa is the usual connectivity symbol. It is shown that if a point v of G has negative cohesiveness, then the set of points adjacent to v is the unique minimum size disconnecting set of G. This theorem has several corollaries including the result that if v has negative cohesiveness in G, then it does not in Γ. Finally we define a cohesiveness triple (n_, n0, n+) of a graph by taking these, respectively, as the number of negative, zero, and positive cohesiveness points of G. The necessary and sufficient conditions for an arbitrary triple to be the cohesiveness triple of a graph are derived.

Abstract The linear arboricity of a graph is the minimum number of linear forests into which its lines can be decomposed. We find that the linear arboricity of every 4‐regular graph is 3. This result enables us to obtain bounds for the linear arboricity of any graph in terms of its maximum degree.

Abstract It is well known that the maximum connectivity k of a graph G with p points and q lines is given by [2 q/p]. This is restated in two useful alternative forms which minimize q given p and k, and which maximize p in terms of q and k. We define the persistence of a graph as the smallest number of points whose removal increases the diameter. It is shown that the persistence of a graph of diameter d is the minimum over all pairs of nonadjacent points of the maximum number of disjoint paths of length at most d joining them. A similar result is obtained for line‐persistence and it is shown that these invariants are independent of each other.

Abstract We investigate the extent to which certain graphical parameters can vary in successive point‐deleted subgraphs. In particular we identify one group of invariants which can be made to conform to an arbitrary monotone nondecreasing sequence and another group to a given nonincreasing sequence. Curiously, the two sets are not disjoint, as the line connectivity is in both. Finally we determine the most general sequences which can appear in this context.

Abstract Simple necessary and sufficient conditions for a list of integers to be the degrees of the points of a tree are wellknown. Unicyclic graphs, which are connected graphs with exactly one cycle, are considered here. A simple set of necessary and sufficient conditions for a list of integers to be the degrees of the points of such a graph is derived.

Abstract Ramsey problems are examined for the different varieties of graphs and digraphs, with and without loops and multiple edges, and even for networks. In every case, the resulting Ramsey number either fails to exist, or has a trivial value, or equals the value for the underlying graph or digraph. Thus it appears there are no new interesting Ramsey numbers for multigraphs and networks.

Abstract A clique of a graph is a maximal complete subgraph. A (p,q)‐graph has p points and q lines. A clique‐extremal (p,q)‐graph has either the maximum or the minimum number of cliques among all (p,q)‐graphs. Moon and Moser have determined constructively the maximum number of cliques in a p‐point graph. The problem of studying the clique‐extremal (p,q)‐graphs is now investigated. We first develop a standard form for such extremal graphs. These standard forms are shown to have a complementary kind of analogy with respect to maximum and minimum.

Abstract A Proper graph G has no isolated points. Its Ramsey number r(G) is the minimum p such that every 2‐coloring of the edges of Kp contains a monochromatic G. The Ramsey multiplicity R(G) is the minimum number of monochromatic G in any 2‐coloring of Kr(G). With just one exception, namely K4, we determine R(G) for proper graphs with at most 4 points. For the stars K1,n, it is shown that R = 2n when n is odd and R = 1 when n is even. We conclude with the conjecture that for a proper graph, R(G) = 1 if and only if G = K2 or K1,n with n even.

The consistency of precedence matrices is studied in the very natural geometric setting of the theory of directed graphs. An elegant recent procedure (Marimont [7]) for checking consistency is further justified by means of a graphical lemma. In addition, the “direction of future work” mentioned in [7] (to which the present communication may be regarded as a sequel) is developed here using graph theoretic methods. This is based on the relationship between the occurrence of directed cycles and the recognition of “strongly connected components” in a directed graph. An algorithm is included for finding these components in any directed graph. This is necessarily more complicated than determining whether there do not exist any directed cycles, i.e., whether or not a given precedence matrix is consistent.

In this survey article, we describe the following topics on electric networks in graph theoretic terms: (1) Kirchhoff's Laws, his mesh and node equations, and his matrix tree theorem, (2) flow problems and Menger's theorem, (3) boolean functions and enumeration and synthesis problems, (4) two-terminal networks, (5) probabilistic problems, (6) sequential machines, and (7) some unsolved problems.

A (binary) relation is a collection of ordered couples. Two relations are isomorphic if there is a 1–1 correspondence between their fields which preserves the ordered couples. Isomorphism between relations is itself an equivalence relation, and a structure is an isomorphism class of binary relations. Carnap ([1], p. 124) asks certain questions concerning (both the exact and) the asymptotic value of the relative frequency that a relation on p objects satisfies certain properties. Among the most interesting special cases are the asymptotic value of the relative frequency that a binary relation on p objects be (a) symmetric, (b) reflexive, (c) transitive irreflexive anti-symmetric, and (d) symmetric irreflexive. These results already appear either in, or almost in, the literature, in various disguises. The object of this expository note is to bring them to light, especially since some of the references may not be generally known to logicians. Carnap ([1], p. 124) points out explicitly the correspondence between binary relations and linear graphs. Davis [2] and Harary [4] obtains precise results for the number of structures with certain properties using the language of relations and graphs respectively; but these do not supply the asymptotic values directly. The asymptotic results which are most useful here are either contained in, or are straight-forward extensions of, the formulas presented in Ford and Uhlenbeck [3], which in turn are based on unpublished work of G. Pólya. In addition, we utilize a result of L. Moser on transitive relations, which appears in Wine and Freund [5].

The object of this note is to classify the isomorphism types of all complete atomic proper relation algebras. In particular we find that the number of abstractly distinct complete atomic proper finite relation algebras of 2m elements is equal to the number of distinct partitions of the positive integer m into summands which are perfect squares. A relation algebra is called complete atomic if its Boolean algebra is complete atomic. A proper relation algebra is a relation algebra whose elements are relations. Lyndon has recently proved, by constructing an appropriate finite relation algebra, that not every complete atomic relation algebra is isomorphic to a proper relation algebra. Henceforth, let us consider a complete atomic proper relation algebra. The atoms {〈a, b〉}, {〈c, d〉} will be called connected if and only if {a, b} ⋂ {c, d} is not empty. Let the relation of connectedness over the set B of all atoms be denoted by ~. For brevity let B = {b1,b2, …}. The relation ~ is obviously reflexive and symmetric. But ~ is not transitive, since a, b, c, d distinct implies {〈a, 0〉} ~ {〈b, c〉}, {〈b, c〉} ~ {〈c, d〉}, and {〈a, b〉} ≁ {〈c, d〉}.