GENERALISED MAXIMAL INDEPENDENCE AND CLIQUE NUMBERS OF GRAPHS

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let β_k, (G) (w_k(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously β_k(G) = w_k([Gbar]). For the sequence m₁ ? m₂ ?…? m_n = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that w_k(G) = m_k for k = 1,2,…,n and w(G) = r (equivalently, β_k(G) = m_k for k = 1,2,…,n and β(G) = r). Define s_k(?,m) to be the largest integer such that for every graph G with at most s_k(?,m) vertices, β_k(G) ? ? or w_k(G) ? m. Exact values for s_k(?,m) if k ≥ 2 and upper and lower bounds for s₁(?,m) are de termined.     

GEODETIC GAMES FOR GRAPHS

ABSTRACT

Let S be a subset of the vertex set V(G) of a nontrivial connected graph G. The geodetic closure (S) of S is the set of all vertices on geodesics between two vertices in S. The first player A chooses a vertex v₁ of G. The second player B then picks v₂ ≠ v₁ and forms the geodetic closure (S₂) = ({v₁, v₂}). Now A selects v₃ ε V—S₂ and forms (S₃) = ({v₁, v₂, v₃}), etc. The player who first selects a vertex v_n such that (S_n) = V wins the achievement game, but loses the avoidance game. These geodetic achievement and avoidance games are solved for several families of graphs by determining which player is the winner.     

A CHARACTERIZATION OF STABLE GRAPHS ON A MAXIMUM(MINIMUM) NUMBER OF EDGES

ABSTRACT

A connected, nontrivial, simple graph of order v is said to be α,β destructible if α,β are factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in α,β-set V'. Graphs which are not α,β destructible for any α,β are called stable, If G is a stable graph on a prime number p ≥ 7 of vertices, then we show that G has a maximum number of edges if and only if G is K_2,p-2, We also characterize stable graphs on a minimum number of edges.     

ON STABLE GRAPHS

ABSTRACT

A connected, nontrivial, simple graph G of order v is said to be α, β destructible if α, β are integral factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in a β-set V'. Graphs which are not α, β destructible for any α,β are called stable. Classes of stable graphs are provided and critically stable graphs of prime order are characterized.     

NETS AND GRAPHS AS PINAL COMPLETIONS AND THE RELATIONS BETWEEN THEM

Abstract

Nets and graphs, both used in Computer Science, are studied from a categorical point of view. It is shown that they may be constructed via final completions of very simple small concrete categories and that their nice properties, namely to form topological categories which are quasitopoi with concrete powers such that products of final maps are final, depend on this fact. Furthermore, the relations between them can be described by means of adjoint functors.     

Forests, colorings and acyclic orientations of the square lattice

There is no known polynomial time algorithm which generates a random forest or counts forests or acyclic orientations in general graphs. On the other hand, there is no technical reason why such algorithms should not exist. These are key questions in the theory of approximately evaluating the Tutte polynomial which in turn contains several other specializations of interest to statistical physics, such as the Ising, Potts, and random cluster models.Here, we consider these problems on the square lattice, which apart from its interest to statistical physics is, as we explain, also a crucial structure in complexity theory. We obtain some asymptotic counting results about these quantities on then ×n section of the square lattice together with some properties of the structure of the random forest. There are, however, many unanswered questions.Supported by a grant from D.G.A.P.A.Supported in part by Esprit Working Group No. 21726, RAND2.     

ON UNIQUELY -G k-COLOURABLE GRAPHS

Abstract

Given graphs F and G and a nonnegative integer k, a map Π: V(F) → + {lm …, k} is a -G k-colouring of F if the subgraphs induced by each colour class do not contain G as an induced subgraph; F is -G k-chromatic if F has a -G k-colouring but no -G (k—1)-colouring. Further, we say F is uniquely -G k-colourable if and only if F is -G k-chromatic and, up to a permutation of colours, it has only one -G k-colouring. Such notions are extensions of the well known corresponding definitions from chromatic theory. In a previous paper (J. Graph. Th. 11 (1987), 87–99), the authors conjectured that for all graphs G of order at least two and all nonnegative integers k there exist uniquely -G k-colourable graphs. We show here that the conjecture holds whenever G or its complement is 2-connected.     

Plücker environments, wiring and tiling diagrams, and weakly separated set-systems

For the ordered set [n] of n elements, we consider the class Bn of bases B of tropical Plücker functions on ²[n] such that B can be obtained by a series of so-called weak flips (mutations) from the basis formed by the intervals in [n]. We show that these bases are representable by special wiring diagrams and by certain arrangements generalizing rhombus tilings on an n-zonogon. Based on the generalized tiling representation, we then prove that each weakly separated set-system in ²[n] having maximum possible size belongs to Bn, yielding the affirmative answer to one conjecture due to Leclerc and Zelevinsky. We also prove an analogous result for a hyper-simplex .     

Matrices with prescribed row,column and block sums

The main result of the paper is Theorem 1. It concerns the sets of integral symmetric matrices with given block partition and prescribed row, column and block sums. It is shown that by interchanges preserving these sums we can pass from any two matrices, one from each set, to the other two ones falling close together as much as possible. One of the direct corollaries of Theorem 1 is substantiating the fact that any realization ofr-graphical integer-pair sequence can be obtained from any other one byr-switchings preserving edge degrees. This result is also of interest in connection with the problem of determinings-complete properties. In the special cases Theorem 1 includes a number of well-known results, some of which are presented.     

ON A CONJECTURE ON nTH ORDER DEGREE REGULAR GRAPHS

Abstract

For n a positive integer and v a vertex of a graph G, the nth order degree of v in G, denoted by deg_nv, is the number of vertices at distance n from v. The graph G is said to be nth order regular of degree k if, for every vertex v of G, deg_nv = k. The following conjecture due to Alavi, Lick, and Zou is proved: For n ≥ 2, if G is a connected nth order regular graph of degree 1, then G is either a path of length 2n—1 or G has diameter n. Properties of nth order regular graphs of degree k, k ≥ 1, are investigated.     

A NOTE ON GRAPHS WHOSE DESTRUCTIONS YIELD COMPLETE SUBGRAPHS

Abstract

A connected graph G of order p =|V| and sise q =| E | is said to be (a_i, b_i)-destructible (with respect to E_i and V_i say) if a_i,b_i are integral factors of p and an a_i-set of edges E_i exists whose removal from G results in exactly b_i components isomorphic to K_i i.e. whose removal from G isolates the vertices in a b_i-set V_i. The operation of removing E_i and V_i from G results in either Ø or a subgraph H of G and is called an (a_i , b_i)-destruction of G. In this paper we show that the only graphs whose every (a_i,b_i)- destruction results in a complete subgraph are K (1,2) and K₄—e, where e ε K₄.     

EXTREMUM AGGREGATES OF MINIMAL 0-DOMINATING FUNCTIONS OF GRAPHS

Abstract

A 0-dominating function 0DF of a graph G = (V,E) is a function f: V → [0,1] such that Σ _xεN(v) f(x) ≥ 1 for each ν ε V with f(v) = 0. The aggregate of a 0DF f is defined by ag(f) = Σ_vεV f(v) and the infimum and supremum of the set of aggregates over all minimal 0DFs of a graph are denoted by γ₀ and Γ₀ respectively. We prove some properties of minimal 0DFs and determine γ₀ and Γ₀ for some classes of graphs.     

ALL GRAPHS ON A NON-PRIME NUMBER OF VERTICES ARE DESTRUCTIBLE

ABSTRACT

A connected, nontrivial, simple graph of order v is said to be α,β destructible if α,β are integral factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in a β-set V'. Graphs which are not α, β destructible for any α.β are called stable. In this paper we prove that all graphs on a non-prime number v of vertices are α,β destructible for some a which divides v.     

Graph factors

This exposition is concerned with the main theorems of graph-factor theory, Hall’s and Ore’s Theorems in the bipartite case, and in the general case Petersen’s Theorem, the 1-Factor Theorem and thef-Factor Theorem. Some published extensions of these theorems are discussed and are shown to be consequences rather than generalizations of thef-Factor Theorem. The bipartite case is dealt with in Section 2. For the proper presentation of the general case a preliminary theory of “G-triples” and “f-barriers” is needed, and this is set out in the next three Sections. Thef-Factor Theorem is then proved by an argument of T. Gallai in a generalized form. Gallai’s original proof derives the 1-Factor Theorem from Hall’s Theorem. The generalization proceeds analogously from Ore’s Theorem to thef-Factor Theorem.     

Bounding the diameter of distance-regular graphs

LetG be a connected distance-regular graph with valencyk>2 and diameterd, but not a complete multipartite graph. Suppose that is an eigenvalue ofG with multiplicitym and that±k. We prove that bothd andk are bounded by functions ofm. This implies that, ifm>1 is given, there are only finitely many connected, co-connected distance-regular graphs with an eigenvalue of multiplicitym.This work was supported by NSERC grant A5367.     

The edmonds—Gallai decomposition for matchings in locally finite graphs

We show that the Edmonds—Gallai decomposition theorem for matchings in finite graphs generalizes to all locally finite graphs. C.N.R.S. Dedicated to Tibor Gallai on his seventieth birthday     

A maximum principle for node voltages in finitely structured,transfinite, electrical networks

Transfinite electrical networks have unique finite-powered voltage-current regimes given in terms of branch voltages and branch currents, but they do not in general possess unique node voltages. However, if their structures are sufficiently restricted, those node voltages will exist and will satisfy a maximum principle much like that which holds for ordinary infinite electrical networks. The structure that is imposed in order to establish these results generalized the idea of local-finiteness. Other properties that do not hold in general for transfinite networks but do hold under the imposed structure are Kirchhoff's current laws for nodes of any ranks and the permissibility of connecting pure voltage sources to such nodes. This work lays the foundation for a theory of transfinite random walks, which will be the subject of a subsequent work.This work was supported by the National Science Foundation under the grants DMS-9200738 and MIP-9200748.     

Improved pebbling bounds

Consider a configuration of pebbles distributed on the vertices of a connected graph of order n. A pebbling step consists of removing two pebbles from a given vertex and placing one pebble on an adjacent vertex. A distribution of pebbles on a graph is called solvable if it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number of a graph, denoted f(G), is the minimal number of pebbles such that every configuration of f(G) pebbles on G is solvable. We derive several general upper bounds on the pebbling number, improving previous results.     

A class of dimension-skipping graphs

Forn≧6 there exists a graphG with dimG=n, dimG*≧n+2, whereG* isG with a certain edge added.