Search

In this paper two main results are obtained. One generalizes the well-known theorem of Erdos and Gallai [1] on the realizability of degree sequences by graphs without loops and multiple edges. It states that a nonincreasing sequence d = (d"1, ..., d"n) of nonnegative integers is r-graphic (that is, realizable by a loopless graph in which no two vertices are joined by more than r edges) if and only if (i) @S^n"i"="1d"i is even, and (ii) for every positive integer k @? n,@?i=1kd"i@?rk(k-1)+@?i=k+1nmin{rk,d"i}The other result is a similar generalization of a theorem of Havel and Hakimi [5, 3].

Every graph appearing in this note is a finite edge graph without loops and multiple edges. Denote by G(n, m) a graph with n vertices and ni edges . K r (t) denotes a graph with r groups of t vertices each, in which two vertices are connected if and only if they belong to different groups . By dividing n vertices into r-1 almost equal groups and connecting the points in different groups one obtains a graph on n vertices with ((r 2)/2(r 1) + u (1)) 11 2 edges which does not contain a Kr(l) . On the other hand, it was shown by Erdős and Stone [7] that ((r 2)/2(r 1) + s) n2 (e > 0) edges assure already the existence of a Kr(t), where t -~ oo as n -p co . This result is the inost essential part of the theorems on the structure of extremal graphs, see e .g. [3], [4], [6], [9] . Let us formulate the result of Erdős and Stone more precisely . Given n, r and e, put rn = [((r-2)/2(r-1)+e)n2] ([x] denotes the integer part of x) and define g(n, r, e) = min {t : every G(n, in) contains a K r (t)} .

This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and manipulating priority queues to achieve a time bound of $O(V\log V + E)$ if V is the number of vertices and E is the number of edges in the graph. This bound compares favorably with the $O(V(V + E))$ time bound of previously known algorithms for finding dominators in arbitrary directed graphs, and with the $O(V + E\log E)$ time bound of a known algorithm for finding dominators in reducible graphs. If $E \geqq V\log V$, the new algorithm requires $O(E)$ time and is optimal to within a constant factor.

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.

K"(r) is the number of those Hamiltonian cycles in the complete digraph on n nodes, each of which has just r edges in common with a particular Hamiltonian cycle, and B(n, r)= n!/{r!(n-r)!}. We show that K"(r)=B(n, r)K"_7(O) and deduce that K,.(O)-(n-l)!e-' for large n and that KJ(r)-(n-1)!e'f1r! if r=o(n). An (n, q) digraph is one with n labelled nodes and q edges. From the result for K"(r), we deduce that, if qn-312--.co as n-o, then almost all (n, q) digraphs are Hamiltonian. If qn-312--oc as n--oo, then the proportion of (n, q) digraphs which are nonHamiltonian is at most I -exp(-c-2) as n. An (n, q) digraph consists of n nodes and q directed edges. We consider only labelled digraphs, i.e. digraphs whose nodes are labelled. If A, B are two different nodes, they may be not joined or joined by the edge AB, or by the different edge BA or by both AB and BA. The greatest possible number of edges is N=n2-n and the (n, N) digraph is called the complete digraph. We write B(h, k)=h!/{k!(h-k)!}, the usual binomial coefficient. Then obviously there are just B(N, q) different (n, q) digraphs. We call a sequence of n edges (1) AIA2, A2A, A3A4, * * * , An-IAnw AnAl, (where A,, * *, A,, are all the different n nodes of the graph) a Hamiltonian cycle (H.c.) and we say that a digraph which contains such a cycle is Hamiltonian. Our principal object is to find (so far as we can) for what q almost all (n, q) graphs are Hamiltonian. We write Kj(r) for the number of H.c. in the complete graph, each of which has just r edges in common with the specified H.c. in (1). The asymptotic approximation to KJ(r) for large n and appropriate r is essential to our method, which is otherwise that used by O'Neil [2] to study the Presented to the Society January 8, 1973 under the title Hamiltonian graphs and digraphs; received by the editors January 10, 1973. AMS (MOS) subject classifications (1970). Primary 05C20.

The properties of a system of bosons interacting through a two body potential composed of a hard repulsive core followed by an attractive square well and having density of the order of that of liquid4He at theλ-point have been studied. The system is found to have a peculiar behaviour around 1 K and we assert that it may have undergone another phase transition around 1 K. Calculations on the effective mass show that them */m values lie between 2 and 9 so that the interacting bosons may have a transition temperature below 1 K. We have also plottedE k vs.k graph for temperatures below 1 K.

Let G be a graph of valency d = 1 + p r n with p prime and n p . It is shown that if the automorphism group of G contains a subgroup A which acts as a regular permutation group on the set of s -arcs in G then s ≤ 7 and s ≠ 6; if d = p r + 1, r = 2 r , v ≥ 1 an integer, p ≠ 2, then s = 1.

A graph of specific volume versus velocity is useful for describing effects in steady, one-dimensional compressible fluid flow through a converging–diverging nozzle. From a thermodynamic point of view there is nothing new in the approach, but it may serve as a useful introduction to the characteristics of compressible flow – particularly the special conditions which prevail at the throat of a choked nozzle.

The four colour conjecture is well known to be equivalent to the proposition that every trivalent planar graph without an isthmus (i.e. an edge whose removal disconnects the graph) has an edge colouring in three colours ([1], p. 121). By an edge colouring we mean an assignment of colours to the edges of the graph so that no two edges of the same colour meet at a common vertex, and the graph is n-valent if n edges meet at each vertex. An edge colouring by three colours is called a Tait colouring; a trivalent graph which has a Tait colouring can be split in three edge-disjoint 1-factors, i.e. spanning monovalent subgraphs.

Using two gamma beams of different energy, bulk densities of water and clay in a clay-water-air mixture were measured simultaneously. From these data the void ratio and the moisture ratio were obtained by calculation. The graph of the void ratio vs the moisture ratio characterizes the shrinkage of the mixture. This shrinkage curve was measured for a bentonite-water-air mixture. Questions concerning the geometry of the sample are discussed.

An (n, q) graph consists of n nodes and q edges, i.e. q distinct unordered pairs of different nodes, so that there are no loops or multiple edges. We write T for the number of unlabelled (n, q) graphs and F for the number of labelled (n, q) graphs. We say that a labelled graph is symmetric if there is a nonidentical permutation of its nodes which leaves the graph unaltered. We write r for the order of the automorphism group of the graph, i.e. the group of all those permutations of the nodes which leave the graph unaltered; we say that the graph is of symmetry order r. A graph which is not symmetric is called asymmetric and, for such a graph, obviously r = 1. We say that an unlabelled graph is symmetric or asymmetric according as the graph obtained by labelling its nodes is symmetric or asymmetric.

A concise, quantitative picture of the state of the art of particle scrubbing is presented in the form of performance prediction methods. A new relationship between the particle diameter collected at 50% efficiency and scrubber pressure drop for several of the most common scrubber types is a design tool of great utility. Scrubber capability for the collection of submicron particles by diffusion is described in a graph for several scrubber types.

The vertices of the graph O k are indexed by the ( k −1)-subsets of a (2 k −1)-set. Two vertices are adjacent if and only if their labelling sets are disjoint. This paper establishes that O 5 is an edge disjoint union of two Hamiltonian circuits and a 1-factor and that O 6 is an edge disjoint union of three Hamiltonian ciruits. It follows that the graphs are 5,6-edge chromatic, respectively. The latter result settles a problem of Biggs about the footballers of Croam.

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.

1. Organic sulfur compounds have a significant inhibiting action on the process of complexing paraffins with urea when the sulfur content of the diesel fuel cut (feedstock) is greater than 0.5%. This gives an appreciable suppression of the activator's role. 2. When the diesel fuel cut is desulfurized to a sulfur content below 0.3–0.4%, it can be processed to yield liquid paraffins containing up to 85–81% C11–C18 straight-chain alkanes. 3. In organizing the routine control of paraffin production in commercial units, a graph relating the yield of liquid paraffins to the total sulfur content of the diesel fuel cuts can be recommended for use.

Frucht [1] gave a method for constructing for each arbitrarily given group a graph whose automorphism group is isomorphic to the prescribed group. Constructions of “product” graphs whose automorphism groups are given subgroups of the wreath product of two groups are given. For S 2 wr G , comprehensive results are given for all subgroups of S 2 wr G containing 1 × G . A concept of graph product which is a generalization of Imrich's definition [2] is employed.

A necessary and sufficient condition is presented for the existence of a solution to the Gotlieb class-teacher timetable problem. Several relationships are established between the class-teacher timetable problem and graphs with preconditions. These preconditions place additional restrictions on the coloration of a graph. The preconditions correspond to the unavailability constraints and preassigned meetings in the class-teacher timetable problem. Using some recent results that convert graphs with preconditions to graphs without them, it is shown that the existence of a coloration of a graph is the required necessary and sufficient condition.

The fundamental equations for a poroelastic material are employed assuming the bodies coming into contact to have a local spherical symmetry. Equations for the stress at timest=0 andt=∞ following the application of the load are derived in closed form. The trajectories of principal stresses are determined and displayed on graphs, the graph att=∞ coinciding qualitatively with the one resulting from Hertz's theory.

A graph X is edge-reconstructible if it is uniquely determined up to isomorphism by the set of graphs X – e obtained by deleting one, edge e. The graphs of a comparatively rich class are shown to be edge-reconstructible. This class contains all non-trivial strong products and certain lexicographic products.

Let G be a finite connected graph with no loops or multiple edges. The point-connectivity K ( G ) of G is the minimum number of points whose removal results in a disconnected or trivial graph. Similarly, the line-connectivity λ( G ) of G is the minimum number of lines whose removal results in a disconnected or trivial graph. For the complete graph K p we have

High‐speed computers have prompted rapid development of courses on the numerical solution of partial differential equations. Solutions of problems on such courses have generally been obtained in the form of lists of numbers from the lineprinter. Such a presentation needs careful study in order to determine the behaviour of the solution and a visual representation of the solution is usually more immediately meaningful to the student. A graphics terminal linked to a computer is particularly well‐suited for providing such output. The type of terminal that appears to be most suitable is a graphical display system capable of operating interactively with the computer. With such a system, a student can view his graphs singly, collectively or superimposed on one another. He also has considerable choice of scale to which he wishes the graph to be displayed. Hard copies of the display can be obtained within about half a minute. Such graphical systems are invaluable in stimulating and maintaining the student's inter...

A matching M of a graph G is a set of edges of G such that each vertex of G is incident with a most one edge of M, and that no edge of G may be added to M without violating this restriction. A number of new results on matchings are obtained, in particular concerning planar and polytopal graphs. A typical result is the following one which deals with (pi bar)(G), the largest possible number of edge-disjoint matchings of G. Theorem: The largest value of (pi bar)(G), possible for 3-polytopal graphs G is 12. (Author)

The graphs considered are connected and bridgeless. For such graphs the existence of two types of connected spanning subgraphs is proved. Applying these results to a connected bridgeless DT-graph (i.e., every line is incident to a point of degree two), G, one obtains the existence of specific Hamiltonian cycles and Hamiltonian paths in G2. In addition it is proved that the square of a connected bridgeless DT-graph is Hamiltonian connected.

The binding number of a graph G, bind(G), is defined; some examples of its calculation are given, and some upper bounds for it are proved. It is then proved that, if bind(G) ≥ c, then G contains at least |G| c (c + 1) disjoint edges if 0 ≤ c ≤ 1 2 , at least | G | (3c − 2) 3c − 2(c − 1) c disjoint edges if 1 ≤ c ≤ 4 3 , a Hamiltonian circuit if c ≥ 3 2 , and a circuit of length at least 3(| G | −1)(c − 1) c if 1 3 2 and G is not one of two specified exceptional graphs. Each of these results is best possible. The Anderson number of a graph is defined. The Anderson numbers of a few very simple graphs are determined; and some rather weak bounds are obtained, and some conjectures made, on the Anderson numbers of graphs in general.

1. A system using “performance graphs” rather than tables or classical Youden plots for displaying laboratory performance is presented. The performance graph is essentially an n-dimensional Youden plot in that it allows the display on the same plot of multiple results at different levels for any given laboratory. 2. The performance of an individual laboratory is evaluated with respect to a data base obtained from laboratories with good performance using well-accepted methods. It is possible, using this system, to develop “cumulative performance graphs” for each constituent for each laboratory. Examples of such graphs are presented which demonstrate laboratory bias and reproducibility. This system is being used in the current Proficiency Testing Program in Clinical Chemistry in Ontario.

We discuss the objection raised by Halliday and Sachrajda against the inclusive sum-rule proof of the vanishing of the triple-Pomeron coupling at zero momentum transfer. We show that the graph which they have examined yields a negative divergent (when s → ∞) contribution to the inclusive cross section. Consideration of an infinite sum of graphs is necessary in order to complete this proof.

Introduction. In [1] the ends of an infinite graph G were introduced; they are the equivalence classes induced by the following equivalence relation on the set ~1 (G) of all one way infinite paths in G: Set U ~V for U, V e ~ I ( G ) if and only if there is a W e ~ I ( G ) meeting both U and V in an infinite number of vertices. The ends of G may be considered as something like improper or figurative vertices of G; the intui t ion behind this consideration of ends as figurative vertices is somewhat related to the idea of the projective closure of an affine plane. B. ZELINKA [3] extends the discussion of connectivity problems in graphs also to these figurative elements. He proves a theorem of Menger type for the special class of free ends in a locally finite graph (see [1], p. 129 for the definition of a free end). I t is the purpose of this note to show t h a t in fact the restriction onto free ends is not necessary.

A graph G is locally n-connected (locally n-edge connected) if the neighborhood of each vertex of G is n-connected (n-edge connected). The local connectivity (local edge-connectivity) of G is the maximum n for which G is locally n-connected (locally n-edge connected). It is shown that if k and m are integers with O ⩽ k < m, then a graph exists which has connectivity m and local connectivity k. Furthermore, such a graph with smallest order is determined. Corresponding results are obtained involving the local connectivity and the local edge-conectivity.

An algorithm to find the Hamiltonian circuit in a bipath network is developed. Using the Hamiltonian circuit all cutsets of a bipath network are generated from incidence sets in a systematic way without duplication. Also it is shown that the algorithm to find the Hamiltonian circuit can be used to test a graph for bipathness.

A graph H is imbedded in a graph G if a subset of the vertices of G determines a subgraph isomorphic to H . If λ ( G ) is the least eigenvalue of G and k R ( H ) = lim sup d→∞ { λ ( G )| H imbedded in G ; G regular and connected; diam( G ) > d ; deg( G ) > d }, then λ(H) − 2 ≤ k R ( H ) ≤ λ( H ) with these bounds being the best possible. Given a graph H , there exist arbitrarily large families of isospectral graphs such that H can be imbedded in each member of the family.

For a graph G, the Ramsey number r(G) is the smallest natural number p such that given a graph H with p points. H or [email protected]? contains a G. An (n,j)-linear forest L is the disjoint union of nontrivial paths, j of which have an odd number of points, and such that the union has n points. If L is an (n,j)-linear forest, then we show that .

The decision problem in which a choice has to be made between two projects, either or both of which may have uncertain outcomes, is shown to reduce to an interpretation of a single graph. Two example problems are considered and their graphs constructed. The technique is finally extended to allow the comparison of any number of projects.

A set of vertices (edges) is called independent if no two vertices (edges) in the set are adjacent. The independence number β(G) (edge independence number β1(G)) is the maximum number of elements in an independent set of vertices (edges) of G. It is shown for any graph G of order p ≥ 3, having complement Ḡ, that [p/2] ≤ β1(G) + β1(Ḡ) ≤ 2[p/2]. From this, upper and lower bounds for β1(G) · β1(Ḡ) are determined. All four bounds are shown to be best possible. It is verified that for every graph G of order p, the bounds β(G) + β(Ḡ) ≤ p + 1 and β(G) · β(Ḡ) ≤ [(p + 1)/2] · {(p + 1)/2} hold and are best possible. Lower bounds for β(G) + β(Ḡ) and β(G) · β(Ḡ) are considered and are shown to be related to Ramsey numbers.

This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm used depth-first search and has O ( V ) time and space bounds, where V is the number of vertices in G . An ALGOL implementation of the algorithm succesfully tested graphs with as many as 900 vertices in less than 12 seconds.

This paper illustrates an algorithm for finding a read-only memory (ROM) specification, optimal in the sense that it results in a minimum ROM bit dimension, starting with an instruction set description which employs acyclic directed graphs. The algorithm selects (by a tabular technique) a descriptive graph subset, shown to be sufficient; then it performs a heuristically guided search among possible solutions generated by the graphs in the subset. The algorithm works for instructions which are such that a microevent occurs at most once in a single instruction; some results apply to the general case as well.

A communication network is modeled by a weighted graph. The vertices of the graph represent stations with storage capabilities, while the edges of the graph represent communication channels (or other information processing media). Channel capacity weights are assigned to the edges of the network. The network is assumed to operate in a store-and-forward manner, so that when a channel is busy the messages directed into it are stored at the station, where it joins a queue that is governed by a first-come first-served service discipline. Assuming that fixed-length messages arrive at random at the network, following the statistics of a Poisson point process, we solve for the steady-state distributions of the message overall delay time, for the average message waiting times at the individual stations, for the average memory size requirements at the stations, as well as for other statistical characteristics of the message flow along a communication path.

In this paper we shall present the concept of a uniquely n-colorable graph, and then introduce a class of graphs which we shall call 6-clique rings. We shall show that 6-clique rings are useful in generating some classes of uniquely 3-colorable graphs. Moreover, we shall demonstrate how the techniques used in producing uniquely 3-colorable graphs from 6-clique rings can be extended to allow the production of other classes of uniquely 3-colorable graphs as well as the production of uniquely n-colorable graphs, where n>3.

Let E be a finite dimensional vector space over the Galois field GF(2). Let lin(E) denote the set of one-dimensional subspaces of E. Let Φ be the symplectic inner product on E. Consider the elements of lin(E) as vertices of a graph, two vertices being connected exactly when they are distinct and orthogonal with respect to Φ. This graph is characterized abstractly.

This paper presents an algorithm which finds a maximum matching in a graph withn nodes andm edges within timek 1 mn+k 2 , wherek1 andk2 are constants. It is also shown that a maximum degree-constrained subgraph can be found within timek 3 m 3 +k 4 , wherek3 andk4, are constants. Use of random access computer is assumed in the computation of the time bounds.

Some of the conceptual implications of the widespread use of the phon curves are discussed and a plot is presented in ‘carpet graph’ form. Arguments for and against use of the sone scale are summarised, followed by a discussion of the relationship between the two scales. To illustrate the implications of this relationship, the effect is shown of combining the information contained in the two scales into a single plot. Finally, to overcome a commonly heard practical objection to the use of the normal sone scale, a logarithmic form is suggested.

In this paper, we give a more general sufficient condition for a degree sequence 〈di〉 to be realizable by a graph (without multiple edges and loops) containing a subgraph of specified degree sequence 〈ki〉. When sequences 〈di〉 and 〈di - ki〉 are both realizable by graphs, it was shown earlier that the condition k ≤ ki ≤ k + 1 for all i and some k ≥ 0 is sufficient for the existence of a 〈di〉-graph containing a 〈ki〉-subgraph. We now show that for k > 1 it is enough to assume, for example, that k ≤ ki ≤ k + 1 holds for all i except possibly i = i0, i1, where ki0 > 0 and ki1 > k + 1.

A report is presented of detailed observations of electrons ranging in energy from 50 to 1000 keV in a relativistic electron precipitation event. The results shown were obtained with the aid of a sounding rocket that was launched at the Andoya rocket range in northern Norway in May 31, 1972. A graph is provided with the differential energy spectrum at a pitch angle of 30 deg for maximum and minimum values.

A new method of deriving high temperature series expansions for the susceptibility of the Ising and classical vector spin models is presented. The method involves generating the expansion for the inverse of the susceptibility, in which case only contributions from star graphs need to be considered. An additional term (the thirteenth) has been added to the Ising high temperature susceptibility series for the FCC lattice. Analysis of the extended series does not indicate that revision of previous critical estimates is required. In a test of the capabilities of the method for other systems, seven terms of the susceptibility series of the FCC Heisenberg and planar vector models have been reproduced. Techniques used in generating the graph data are discussed.