Search

We prove that the semigroup of all isotonic transformations of an infinite partially ordered set is nondenumerable. We construct an example of a reflexive graph, the semigroup of all isotonic transformations of which is denumerable.

Relations are established characterizing the connection between recursiveness with respect to consistent functionals and Rc-operations known in the theory of sets. It is pointed out that the graph of a functional that is partial recursive with respect to a given consistent functional F can be obtained by a certain (appropriate to F) Rc-operation. Sets obtained by a given Rc-operation over general recursive sets are characterized as semirecursive with respect to a certain (appropriate to this Rc-operation) consistent functional.Bibliography: 15 items.

A graph is magic if the edges are labeled with distinct nonnegative real numbers such that the sum of the labels incident to each vertex is the same. Given a graph finite G, an Abelian group g, and an element r(v) ∈ g for every v ∈ V(G), necessary and sufficient conditions are given for the existence of edge labels from g such that the sum of the labels incident to v is r(v). When there do exist labels, all possible labels are determined. The matroid structure of the labels is investigated when g is an integral domain, and a dimensional structure results. Characterizations of several classes of graphs are given, namely, zero magic, semi-magic, and trivial magic graphs.

The CI chondrites are the most volatile-rich meteorites. Relative to the CI chondrites, the ordinary chondrites have lower abundances of refractory and volatile elements. Four types of fractionations are summarized in a table. Ordinary-chondrite/CI abundance ratios for moderately volatile elements in H- and L-group chondrites are presented in a graph. Possible explanations for the observed relations are considered, giving attention to several processes which could result in the separation of nebular solids and gases.

Let G be a connected 1-transitive graph of valency five. It is shown that the order of a vertex stabilizer divides 5 · 3 2 · 2 17 . A theorem of A. Gardiner bounding the order of a vertex stabilizer of a 2-transitive graph of valency 1 + p , p prime, is reproved.

A class of cubic graphs is introduced for which the genus is a nonadditive function of the genus of subgraphs. This provides a small (28 node) counterexample to Duke’s conjecture concerning the relation of the Betti number to the genus of a graph.

This paper is concerned with the extraction of two-dimensional line structures from real photographs of both flat-faced and curved objects. Initially, the photograph is subjected to a nonlinear transformation that produces a two-dimensional stroke array. The strokes, which are weighted short vectors, are assembled into structures called streaks using graph searching techniques. Streaks are digital curves which exhibit polygonal as well as cellular properties. They are classified into prime, parasitic, and blurred streaks. The prime streaks are extended along second-order curves to form junctions, and are built into a line structure. The procedure was successfully tested on a variety of real photographs of dull- and shiny-surfaced objects. It can easily be optimized for a given class of images.

Any term or symbol undefined in this paper is defined in [5]. For graphs F and G, G > F means G contains a subgraph isomorphic to F and E(G) denotes the edge set of G. If E ⊆ E(G), 〈E〉 is the subgraph of G whose edge set is E and whose vertex set is that subset of vertices of G which are incident with edges in E.

New data are presented on the reactions π − p→ π + π − n, π − p→ π − π 0 p at 415 MeV/ c incident momentum. These data, together with events at higher momenta, are analysed using the isobar model of Deler and Valladas. The I = J = 0 ππ interactions is represented by a function of the ππ mass, and the scattering, a 0 0 , has been determined. One finds a value consistent with zero and −0.06 m π −1 a 0 0 m π −1 . Certain features of the fit are investigated in terms of a rescattering graph.

In recent papers D. R. Lick and A. T. White have introduced point partition numbers as generalizations of the chromatic number and the point-arboricity of a graph. In particular they proved that an analogue of Heawood’s theorem holds for the point partition numbers. In the present paper it is shown that the bounds provided by their result may be improved for graphs of large girth. Finally, using a method of Erdös, it is shown that there exist graphs with large girth and large point-partition number.

Holton (1973) introduced the following concept. A graph G is semi-stable if there exists a point v in G for which Γ(Gv) = Γ(G)v: where Γ(G) is the automorphism group of G, Gv is the graph G with v deleted and Γ(G)v is the subgroup of Γ(G) that fixes v. We say G is semi-stable at v. A partial stabilising sequence in Gs1, v2,…vk of its points such that Γ(G)v1v2…vi ═ Γ(Gv1v2…v1) for i = 1,2,…,k. If there exists a partial stabilising sequence in G for which k equals the number of points of G then G is said to be stable (Holton (1973a)). Most natation and terminology in what follows is explained in Harary (1969).

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.

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 dependence of Huckel π-electron energies, E π , on the basic graph theoretical parameters N (the number of vertices), ν (the number of edges) and ASC (the algebraic structure count) is explored. The form with the ASC enters E π is established and an equation for E π is developed. It is shown how the early and apparent success of the (resonance) theory rested on the fortunate fact that all Kekule structures for benzenoid hydrocarbons and acyclic polyenes have the same parity. The significance of ASC in determining chemical stability and reactivity is dicussed briefly.

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.

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.

We show how to make s-channel unitarity cuts through an arbitrary graph involving bare pomerons.

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.

Taking advantage of techniques developed in the field of Computer Science, a laboratory based on a minicomputer system has been generated for the general purpose simulation of analog and digital communication systems. Using a graphics terminal, a student user may specify the characteristics of his desired system and then dynamically examine time and frequency domain displays as the information-bearing signal propagates through his system. The system user describes his system initially in terms of an Information Flow graph which identifies all system nodes, their interconnections, and characteristics. This graph is then represented in the simulation as a chained User Program. The execution of that User Program simulates the communication system. Emphasis in this system is placed on the ability to model physical processes and the use of graphical displays to relate the model to the process itself. In addition, the characteristics of a minicomputer facility to duplicate the simulation system discussed here are presented.

A formula is obtained for the global flow of information in a discrete Markov system which is defined on a locally finite graph. It is shown that the information flow is related to a random walk on the lattice of finite subgraphs of the graph.

A complete diallel cross was made among eight homozygous barley genotypes. Four of the parents were commercially grown cultivars and the remaining four consisted of isogenic derivatives of a California cultivar, Atlas. In a replicated experiment grown in two seasons, measurements were recorded on days to heading, days to maturity, plant height, grain yield and seed size. These data were then used to estimate variances (Vr) and covariances (Wr) of arrays in each season and a genetical interpretation of the relations between these statistics was sought. For days to heading, days to maturity and plant height, the Wr/Vr graphs provided an evaluation of genetic relationship among the parental genotypes. As expected on the basis of their known genetic similarity, the isogenic lines of Atlas were close together on the Wr/Vr graph. Contrary to the expectation, however, remarkable similarity among the commercially grown genotypes was indicated by the proximity of the array points representing them. The patterns of distribution of the array points were such that the eight parents could be classified into two well-separated groups, one comprising the isogenic lines which carried most of the dominant alleles and the other comprising the cultivars carrying largely the recessive alleles. A seasonal difference in the genetic behaviour of the parents was also observed. Although some of the observed genetic differences between the two parental groups in one season disappeared in the following season, the positions of the array points were consistent in depicting substantial differences between the groups in both seasons. In most cases a graphical analysis was possible when a number of parents were removed from the diallel table. Non-random distribution of genes among the parents did not appear to be a common cause of disturbance in the relations between Wr and Vr even when the number of parents were very small. For two economically important characters, kernel size and grain yield, a graphical analysis was not possible, presumably because of the failure of a number of hypotheses underlying the analysis.

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 paper presents an algorithm for partitioning the nodes of a weighted graph in order to minimize the interset weights. The algorithm is patterned after the branch-and-probabilistic-bound procedures of Graves and Whinston. Final partitions or solutions are characterized by probability statements like: “the probability is greater than α that a randomly selected solution is inferior to the final.” The algorithm can be used to segment computer programs and data libraries when statistics on the transition or reference rates among program or data elements are known. Numerical results demonstrate the feasibility of efficiently partitioning 50-node graphs.

For the conventional Hubbard model system, the static magnetic susceptibility and the local magnetic moments are studied by means of the functional integral technique. Expanding functional integrals in the lattice space, the magnetic susceptibility, and the local moment are represented by graph series. Looking for the dependence of magnetic properties on the parameters of the model Hamiltonian, a phase diagram is obtained. The stability of the phases is considered. For special parameter values of the model system the phase diagram can be compared qualitatively with the diagram obtained experimentally for V2O3. Die statische magnetische Suszeptibilitat sowie die lokalen magnetischen Momente werden fur das einfache Hubbard-Modell mit Hilfe der Methode der funktionalen Integration untersucht. Nach der Entwicklung der funktionalen Integrale im Gitterraum werden fur beide Grosen Graphenreihen angegeben. Die Abhangigkeit der magnetischen Eigenschaften von den Modellparametern fuhrt zur Konstruktion eines Phasendiagramms. Die Stabilitat der Phasen wird untersucht. Fur spezielle Parameterwerte des Modellsystems ist dieses Phasendiagramm in qualitativer Hinsicht mit dem experimentell fur V2O3 erhaltenen Diagramm vergleichbar.

This paper establishes a connection between a certain class of Ramsey numbers for graphs and the class of symmetric block designs admitting a polarity. The main case considered here relates the projective planes over Galois fields to the Ramsey numbers R ( C 4 , K 1 , n ) = f ( n ) R({C_4},{K_{1,n}}) = f(n) . It is shown that, for every prime power q , f ( q 2 + 1 ) = q 2 + q + 2 q,f({q^2} + 1) = {q^2} + q + 2 , and f ( q 2 ) = q 2 + q + 1 f({q^2}) = {q^2} + q + 1 .

A simple automatic digitizer for graphs and polaroid pictures for use with minicomputers has been developed. This system comprises a slightly modified commercial TV camera, a digitizer that processes the TV video signals and delivers in a digital form a sequence of the ordinates of the analyzed graph, and an optional TV monitor and CRT oscilloscope interfaced to the minicomputer. Special software which acquires the digitized data and corrects for improper alignments and aberrations caused by the TV camera was written. This software permits the composition of the system from common elements present in most laboratories.

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k⩾3), 3k vertices (k⩾5) and 5k vertices (k⩾4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.

Let G"r(n) be an r-chromatic graph with n vertices in each colour class. Suppose G = G"3(n), and @d(G), the minimal degree in G, is at least n + t(r >= 1). We prove that G contains at least t^3 triangles but does not have to contain more than 4t^3 of them. Furthermore, we give lower bounds for s such that G contains a complete 3-partite graph with s vertices in each class. Let @?"r(n) = max {@d(G): G = G"r(n), G does not contain a complete graph with r vertices}. We obtain various results on @?"r(n). In particular, we prove hat if c"r = lim"n"->"[email protected]?"r(n)n, then lim"r"->"~(c"r - (r - 2)) >= 12 and we conjecture that equally holds. We prove several other results and state a number of unsolved problems.

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.

In papers (7, 8), Vizing studied graphs which are critical with respect to edge colourings. In particular, he obtained bounds on the number of edges and on the circuit length of such graphs in terms of its maximum valency. The object of this paper is to improve these bounds by obtaining others which also take into account the order of the graph.

The graphs considered here are finite and have no loops or multiple edges. In particular, Km denotes the complete graph on m vertices. For any graph G,V(G) and E(G) denote, respectively, the vertex and edge sets of G. A forest is a graph which has no cycles and a tree is a connected forest. The reader is referred to [1] or [4] for the meaning of terms not defined in this paper.

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...

In recent years there has been great development in the area becoming known as Ramsey Theory. In this paper we explore some restricted Ramsey theorems, best illustrated by the following beautiful result of NeSetIil and RodI. We begin with the first nontrivial example of the original theorem of Ramsey: Given any two-coloring of the edges of KB there exists a monochromatic triangle. Let us use the notation H--f (G), if any c-coloring of the edges of a graph H yields a monochromatic G. In this instance we write K, -+ (K& . It was asked, by P. Erdos, what graphs H have the property H--f (K& , and whether such H exist if you restrict the clique number w(H). In an elegant, though complex, paper Folkman [4] showed that there exist H satisfying H---f (K& , where w(H) = 3. A full generalization, using a totally different method, was given by NeSetIil and Rod1 [6], who showed that for all G, c there exists a graph H so that H -+ (G), and w(H) = w(G).

This paper is a review of the state of the art in the area of computer-aided reliability and safety analysis. It covers both reliability graph analysis and fault tree analysis. By comparing the methods developed for reliability graph analysis with those of fault tree analysis, it is seen that the two fields have been developed rather independently and yet a unified view and a more integrated approach to the problem is shown to be possible. Several new algorithms developed by the authors are given which detect minimal path and cut sets from a reliability graph and a fault tree.

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.

This paper presents an evaluation of site quality based on the relationship between volume per square foot of basal area and age of plantation, for planted red pine (Pinus resinosa Ait.) in Quebec.A graph for the three site index classes is included with indication for its use. There is a table showing the values of volume per square foot of basal area as a function of average height and average form quotient of a stand, permitting a rapid evaluation of stand volume of a plantation. Finally, several factors affecting growth and yield of red pine plantations for various sites in Quebec are discussed.

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.

In this paper we provide a simple sufficient condition for the existence of an edge-disjoint packing in a graph for three trees of specified degree sequence. The condition is similar to the one given earlier for packing of two trees of specified degree sequence. The proof of the main theorem is by giving a procedure for constructing the packing.