The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The authors have previously introduced a family of graphs possessing "average minimum path length" as a useful model for an idealized computer network. The present paper gives a detailed determination of all non-isomorphic members of the family up to 14 nodes. Results, to appear in a later paper, are announced for graphs up to 34 nodes.
A balanced weighing matrix is a square orthogonal matrix of 0’s, 1’s and −1’s such that the matrix obtained by squaring entries is the incidence matrix of a (v, k, λ) configuration. Properties of cyclically generated and group generated configurations are discussed and certain natural questions arising are disposed of by theory or counter-example. Matrices of low order are tabulated.
This paper studies the family of cyclic sequences of edges (of a connected plane graph) obtained by walking on edges in such a way that the next edge is, alternately, the one that is leftmost or rightmost with respect to the current edge.
The chromial or chromatic polynomial of a finite graph G is a polynomial P(G,λ) in a variable λ with the following property: the value of P(G,λ) when λ is a positive integer is the number of ways of colouring G in λ colours. In this paper various properties of the chromial, considered as a function of a real variable λ, are discussed.
Four tournaments of the king of the castle type are introduced and by means of numerical studies and computer simulation compared with the round robin and some other tournaments. The structure of our tournaments together with their favourable performance in predicing the best player suggests to the authors that tournaments of this type are sound practical alternatives to round robins.
Given a table of n rows and p columns, with only some of the cells occupied, how may the rows and columns be interchanged so that the maximum number of occupied cells are adjacent? This problem arises in correlation studies such as host-parasite relationships.
The Stanton-Mullin classification of BIBDs into (v,k) families has been extended by Collens to produce BIBSYS, an automatic system for storage, retrieval, and generation of BIBDs. The resulting tables show quite a few gaps in our knowledge concerning existence of early entries in the table. This paper describes an algorithm which has been successfully used to generate initial difference blocks which...
One-factors of the complete graph K2r on 2r vertices are considered. A set S of less than 2r-1 of these one-factors is called maximal if they are pairwise edge-disjoint, and if there is no one-factor of K2r which is edge-disjoint from all members of S. It is shown that a maximal set in K2r must contain at least r one-factors, and that if r is even then the smallest possible maximal set has...
A taxonomist may use rooted trees to depict hierarchical classifications of species belonging to the same family. We look at various properties which might be required of a "coefficient of similarity" to be used to compare the shapes of two such trees. A similarity measure calculated from the number of shared subtrees is found to satisfy these requirements.
It is well known in random walk theory that the probability of a return to the origin at epoch 2n equals the probability of no return to the origin. Quite satisfying algebraic proofs exist, but Feller has popularised geometrical proofs which snip, reflect and slide portions of the graph of the random walk. We here suggest improved versions of two such proofs.
The probability that precisely r out of n overlapping events shall occur is $$S_r - \left( {\begin{array}{*{20}c}{r + 1} \\r \\\end{array} } \right)S_{r + 1} + \left( {\begin{array}{*{20}c}{r + 2} \\r \\\end{array} } \right)S_{r + 2} - \ldots \pm \left( {\begin{array}{*{20}c}n \\r \\\end{array} } \right)S_n$$ . This result and the related result for the ‘tail’ probability that more than r shall occur...
In this paper we give a detailed survey of stability properties of various combinations of graphs. We review previous work on unions, joins and (cartesian) products of graphs, and supply further evidence of the unpredictability of the stability index function under cartesian products in that we show that for r>2, the r-cube has stability index 1, which for most values of m and n the product...
A q-star is a connected graph with q edges and in which every vertex but one has valency 1. This paper concerns the question of which particular complete graphs can be decomposed into q-stars that have pairwise disjoint edge-sets for the values of q, 6 and 10. It is shown that the complete graphs on m vertices can be decomposed into 6-stars if and only if m is greater than or equal to 12 and m ≡ 0,1,4,9...
Some problems concerning the stability index of the permutation graph (Pn, π) are investigated. It is shown that for a certain class of permutation graphs, called Roman numerals, the stability index can be only 2n, 2n − 4, 2n − 5, 2n − 6 or 2n − 7. The general situation for (Pn, π) is more complicated and some open questions are listed.
Four circulant (or type 1) (0,1,−1) matrices X1, X2, X3, X4 of order t with the property that each of the t2 positions is non-zero in precisely one of the Xi and such that $$X_1 X_1 ^T + X_2 X_2 ^T + X_3 X_3 ^T + X_4 X_4 ^T = tI_t$$ will be called T-matrices. This paper studies the construction, use and properties of T-matrices giving a new construction for Hadamard matrices and some new...
We introduce a conjectured characterisation of planar graphs in terms of the structure of the circuits of a graph, and we confirm that conjecture in one direction.
Properties of individual non-terminal symbols in context-free grammars are of interest in the fields of compiling and artificial intelligence. This paper describes an algorithm which will find, for all the non-terminal symbols in any context-free grammar, the shortest string which consists only of terminal symbols which can be produced from each non-terminal symbol by application of the rules of the...
Finite generalized Hall planes possessing elations which are not translations for more than one centre on the translation line are investigated. The existence of such elations is related to the structure of certain coordinate systems and the precise set of points that are centres of such elations is determined. A method of constructing planes possessing such elations is elaborated and then applied...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.