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.     

The binding number of a graph and its triangle

In this paper we prove the following conjecture of Woodall^[1]: if bind (G)3/2, thenG contains a triangle. Moreover we also prove that if bind (G)3/2, then each vertex is contained in a 4-cycle, each edge is contained in a 5-cycle whenV(G)11, and there exists a 6-cycle inG.     

The binding number of a graph and its pancyclism

The binding number is an important parameter of a graph.The binding number of a graph G,bind (G),is the largest real number c such that|N(X)|=min(c|X|,|V(G)|) for every X(?)V(G).In this paper,we prove the Woodall's conjecture:In bind (G)≥3/2,then G is pancyclic;andobtain some interesting results.     

The binding number of a graph and its cliques

We consider the binding numbers of K_r-free graphs, and improve the upper bounds on the binding number which force a graph to contain a clique of order r. For the case r=4, we provide a construction for K₄-free graphs which have a larger binding number than the previously known constructions. This leads to a counterexample to a conjecture by Caro regarding the neighborhoods of independent sets.     

Bounding the number of circuits of a graph

Letc(G) denote the number of circuits of a graphG. In this paper, we characterize those minor-closed classesG of graphs for which there is a polynomial functionp(.) such thatc(G)p(|E(G)|) for all graphsG inG.     

The minimum number of subgraphs in a graph and its complement

For a graphb F without isolated vertices, let M(F; n) denote the minimum number of monochromatic copies of F in any 2-coloring of the edges of K_n. Burr and Rosta conjectured that when F has order t, size u, and a automorphisms. Independently, Sidorenko and Thomason have shown that the conjecture is false. We give families of graphs F of order t, of size u, and with a automorphisms where . We show also that the asymptotic value of M(F; n) is not solely a function of the order, size and number of automorphisms of F. © 1929 John Wiley & Sons, Inc.     

The semi-chromatic number of a graph

We introduce the notion of the semi-chromatic number of a graph with a nonempty number of edges. Then we prove that the difference between the semi-chromatic number and the half of the chromatic number is at most 1.     

The basis number of a graph

MacLane proved that a graph is planar if and only if it has a 2-fold basis for its cycle space. We define the basis number of a graph G to be the least integer k such that G has a k-fold basis for its cycle space. We investigate the basis number of the complete graphs, complete bipartite graphs, and the n-cube.     

The Hoffman number of a graph

For a connected graph G with n vertices, let {λ₁,λ₂,…,λ_r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ(G) of G is defined by μ(G)=λ₁λ₂…λ_r/n. In this paper, we study some properties and applications of the Hoffman number.     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D₉, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).     

Toughness,binding number and restricted matching extension in a graph

A connected graph $G$ with at least $2m+2n+2$ vertices is said to satisfy the property $E(m,n)$ if $G$ contains a perfect matching and for any two sets of independent edges $M$ and $N$ with $\left|M\right|=m$ and $\left|N\right|=n$ with $M\cap N=?$, there is a perfect matching $F$ in $G$ such that $M?F$ and $N\cap F=?$. In particular, if $G$ is $E(m,0)$, we say that $G$ is $m$-extendable. One of the authors has proved that every $m$-tough graph of even order at least $2m+2$ is $m$-extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for $m$-extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee $E(m,n)$.     

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph has been studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is not smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.     

The book crossing number of a graph

Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are two polynomial time algorithms to generate near optimal drawing of G on books. The first algorithm give an O(log² n) times optimal solution, on small number of pages, under some restrictions. This algorithm also gives rise to the first polynomial time algorithm for approximating the rectilinear crossing number so that the coordinates of vertices in the plane are small integers, thus resolving a recent open question concerning the rectilinear crossing number. Moreover, using this algorithm we improve the best known upper bounds on the rectilinear crossing number. The second algorithm generates a drawing of G with O(m²/k²) crossings on k pages. This is within a constant multiplicative factor from our general lower bound of Ω(m³/n²k²), provided that m = Ψ(n²). © 1996 John Wiley & Sons, Inc.