Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

The binding number of a graph and its Anderson number

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 $\text{|G|}\text{c}\text{(c + 1)}$ disjoint edges if $\text{0 ≤ c ≤}\text{1}\text{2}$, at least $\text{| G |}\text{(3c ? 2)}\text{3c}\text{?}\text{2(c ? 1)}\text{c}$ disjoint edges if $\text{1 ≤ c ≤}\text{4}\text{3}$, a Hamiltonian circuit if $\text{c ≥}\text{3}\text{2}$, and a circuit of length at least $\text{3(| G | ?1)(c ? 1)}\text{c}$ if $\text{1 < c ≤}\text{3}\text{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.     

On the radius of graphs

Let G be any 3-connected graph containing n vertices and r the radius of G. Then the inequality $\text{r <}\text{1}\text{4}\text{n + O(}\text{log}\text{n)}$ is proved. A similar theorem concerning any (2m ?1)-connected graph G can be proved too.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

On a conjecture of bondy

Bondy conjectured [1] that: if G is a k-connected graph, where k ≥ 2, such that the degree-sum of any k + 1 independent vertices is at least m, then G contains a cycle of length at least: $\text{Min}\text{(}\text{2m}\text{(k + 1)}\text{, n)}$ (n denotes the order of G). We prove here that this result is true.     

The number of Hamiltonian circuits

G = 〈V(G), E(G)〉 denotes a directed graph without loops and multiple arrows. $\text{K}$(G) denotes the set of all Hamiltonian circuits of G. Put H(n, r) = max{|E(G)|, |V(G)| = n, 1 ≤ |$\text{K}$(G)| ≤ r}. Theorem: $\text{H(n, 1) = (}\text{n}{}^2\text{2}\text{) + (}\text{n}\text{2}\text{) ?1}$. Further, H(n, 2),…, H(n, 5) are given.     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

Group ramsey theory

A subset S of a group G is said to be a sum-free set if $\text{S ∩ (S + S) = ?}$. Such a set is maximal if for every sum-free set T ? G, we have |T| ? |S|. Here, we generalize this concept, defining a sum-free set S to be locally maximal if for every sum free set T such that S ? T ? G, we have S = T. Properties of locally maximal sum-free sets are studied and the sets are determined (up to isomorphism) for groups of small order.     

A lower bound for the independence number of a planar graph

A subset of the vertices of a graph is independent if no two vertices in the subset are adjacent. The independence number α(G) is the maximum number of vertices in an independent set. We prove that if G is a planar graph on N vertices then $\text{α(G)/N ?}\text{2}\text{9}$.     

A fundamental region for Hecke's modular group

Hecke proved analytically that when λ ≥ 2 or when $\text{λ = 2}\text{cos}\text{(}\text{π}\text{q}\text{)}$, q ∈ Z, q ≥ 3, then $\text{B(λ) = {τ:}\text{Im}\text{τ > 0, |}\text{Re}\text{τ| <}\text{λ}\text{2}\text{, |τ| > 1}}$ is a fundamental region for the group G(λ) = 〈S_λ, T〉, where S_λ: τ → τ + λ and $\text{T: τ →}\text{?1}\text{τ}$. He also showed that B(λ) fails to be a fundamental region for all other λ > 0 by proving that G(λ) is not discontinuous. We give an elementary proof of these facts and prove a related result concerning the distribution of G(λ)-equivalent points.     

On the minimum order of graphs with given semigroup

Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that $\text{2}\text{(1 + o(1))n}\text{log}{}_2\text{n}\text{≤M(n)≤n ·}\text{2n}\text{+ O(n)}$. Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log₂n + n vertices such that End(G) is isomorphic to M.     

Arbres avec un nombre maximum de sommets pendants

This article is an attempt to study the following problem: Given a connected graph G, what is the maximum number of vertices of degree 1 of a spanning tree of G? For cubic graphs with n vertices, we prove that this number is bounded by $\text{1}\text{4}\text{n}$ and $\text{1}\text{2}\text{(n ? 2)}$.     

Lower bounds on the independence number in terms of the degrees

Wei discovered that the independence number of a graph G is at least Σ_v(1 + d(v))^?1. It is proved here that if G is a connected triangle-free graph on n ≥ 3 vertices and if G is neither an odd cycle nor an odd path, then the bound above can be increased by $\text{n}\text{Δ(Δ + 1)}$, where Δ is the maximum degree. This new bound is sharp for even cycles and for three other graphs. These results relate nicely to some algorithms for finding large independent sets. They also have a natural matrix theory interpretation. A survey of other known lower bounds on the independence number is presented.     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

Contributions to the theory of domination,independence and irredundance in graphs

A vertex x in a subset X of vertices of an undirected graph is redundant if its closed neighbourhood is contained in the union of closed neighbourhoods of vertices of X?{x}. In the context of a communications network, this means that any vertex which may receive communications from X may also be informed from X?{x}. The lower and upper irredundance numbers ir(G) and IR(G) are respectively the minimum and maximum cardinalities taken over all maximal sets of vertices having no redundancies. The domination number γ(G) and upper domination number Γ(G) are respectively the minimum and maximum cardinalities taken over all minimal dominating sets of G. The independent domination number i(G) and the independence number β(G) are respectively the minimum and maximum cardinalities taken over all maximal independent sets of vertices of G.A variety of inequalities involving these quantities are established and sufficient conditions for the equality of the three upper parameters are given. In particular a conjecture of Hoyler and Cockayne [9], namely $\text{i+β?2p + 2δ - 2}\text{2pδ}$, is proved.     

On complementary graphs with no isolated vertices

Let $\text{G}$ denote the complement of a graph G, and x(G), β₁(G), β₄(G), α₀(G), α₁(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order $\text{p}\text{, {2√p} ? x(G) + x(}\text{G}\text{) ? p + 1}\text{and p}\text{? x(G)·x(}\text{G}\text{) ? [(}\text{1}\text{2}\text{(p + 1))}{}^2\text{]}$. Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β₁(G) + α₁(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of $\text{G}\text{and}\text{G}$, since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both $\text{G}\text{and}\text{G}$ contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G.     

Symmetric hyperbolic difference schemes and matrix problems

Sufficient conditions for the stability of multidimensional finite difference schemes are difficult to obtain. It is shown that for special families of amplification matrices G (A, B) a sufficient condition for power boundedness can be obtained by replacing the matrices by appropriate scalars, and so the problem is reduced to a scalar one. As one application it is shown that the Lax-Wendroff scheme in two dimensions is stable if |Au|^{$\text{2}\text{3}$} + |Bu|^{$\text{2}\text{3}$} ? 1 for all real unit vectors u. The Lax- Wendroff scheme with stabilizer does not always permit such large time steps. It is conjectured that the analysis for all symmetric hyperbolic schemes can be reduced to the scalar case.     

Results on the edge-connectivity of graphs

It is shown that if G is a graph of order p ≥ 2 such that deg u + deg v ≥ p ? 1 for all pairs u, v of nonadjacent vertices, then the edge-connectivity of G equals the minimum degree of G. Furthermore, if deg u + deg v ≥ p for all pairs u, v of nonadjacent vertices, then either p is even and G is isomorphic to $\text{K}{}_{\mathrm{<mtext>p</mtext><mtext>2</mtext>}}\text{× K}{}_2$ or every minimum cutset of edges of G consists of the collection of edges incident with a vertex of least degree.