The independence polynomial of graph \(G\) is the function \(i(G, x) = \sum i_k x^k\), where \(i_k\) is the number of independent sets of cardinality \(k\) in \(G\). We ask the following question: for fixed independence number \(\beta\), how large can the modulus of a root of \(i(G, x)\) be, as a function of \(n\), the number of vertices? We show that the answer is \((\frac{n}{\beta})^{\beta – 1} + O(n^{S-2})\).

Balance has played an important role in the study of random graphs and matroids. A graph is balanced if its average degree is at least as large as the average degree of any of its subgraphs. The density of a non-empty loopless matroid is the number of elements of the matroid divided by its rank. A matroid is balanced if its density is at least as large as the density of any of its submatroids. Veerapadiyan and Arumugan obtained a characterization of balanced graphs; we extend their result to give a characterization of balanced matroids.

We show that there is a straight line embedding of the complete graph \(K_C\) into \(\mathcal{R}^3\) which is space-filling: every point of \(\mathcal{R}^3\) is either one of the vertices of \(K_C\), or lies on exactly one straight line segment joining two of the vertices.

An efficient algorithm for computing chromatic polynomials of graphs is presented. To make very large computations feasible, the algorithm combines the dynamic modification of a computation tree with a hash table to store information from isomorphically distinct graphs that occur during execution. The idea of a threshold facilitates identifying graphs that are isomorphic to previously processed graphs. The hash table together with thresholds allow a table look-up procedure to be used to terminate some branches of the computation tree. This table lookup process allows termination of a branch of the computation tree whenever the graph at a node is isomorphic to a graph that is stored in the hash table. The hashing process generates a large file of graphs that can be used to find any chromatically equivalent graphs that were generated. The initial members of a new family of chromatically equivalent graphs were discovered using this algorithm.

In this paper, we investigate the sufficient conditions for a graph to contain a cycle (path) \(C\) such that \(G\) – \(V(C)\) is a disjoint union of cliques. In particular, sufficient conditions involving degree sum and neighborhood union are obtained.

Let \(k\) and \(d\) be integers with \(d \geq k \geq 4\), let \(G\) be a \(k\)-connected graph with \(|V(G)| \geq 2d – 1\), and let \(x\) and \(z\) be distinct vertices of \(G\). We show that if for any nonadjacent distinct vertices \(u\) and \(v\) in \(V(G) – \{x, z\}\), at least one of \(yu\) and \(zv\) has degree greater than or equal to \(d\) in \(G\), then for any subset \(Y\) of \(V(G) – \{x, z\}\) having cardinality at most \(k – 1\), \(G\) contains a path which has \(x\) and \(z\) as its endvertices, passes through all vertices in \(Y\), and has length at least \(2d – 2\).

For a graph \(G\), a partiteness \(k \geq 2\) and a number of colours \(c\), we define the multipartite Ramsey number \(r^c_k(G)\) as the minimum value \(m\) such that, given any colouring using \(c\) colours of the edges of the complete balanced \(k\)-partite graph with \(m\) vertices in each partite set, there must exist a monochromatic copy of \(G\). We show that the question of the existence of \(r^c_k(G)\) is tied up with what monochromatic subgraphs are forced in a \(c\)-colouring of the complete graph \(K_k\). We then calculate the values for some small \(G\) including \(r^2_3(C_4) = 3, r^2_4(C_4) = 2, r^3_3(C_4) = 7\) and \(r^2_3(C_6) = 3\).

A graph \(G\) with vertex set \(V(G)\) is an exact \(n\)-step domination graph if there is some subset \(S \subseteq V(G)\) such that each vertex in \(G\) is distance \(t\) from exactly one vertex in \(S\). Given a set \(A \subseteq \mathbb{N}\), we characterize cycles \(C_t\) with sets \(S \subseteq V(C_t)\) that are simultaneously \(a\)-step dominating for precisely those \(a \in A\). Using Polya’s method, we compute the number of \(t\)-step dominating sets for a cycle \(C_t\) that are distinct up to automorphisms of \(C_t\). Finally, we generalize the notion of exact \(t\)-step domination.

Let \(D\) be a digraph. The competition-common enemy graph of \(D\) has the same set of vertices as \(D\) and an edge between vertices \(u\) and \(v\) if and only if there are vertices \(w\) and \(x\) in \(D\) such that \((w,u), (w,v), (u,x)\), and \((v,x)\) are arcs of \(D\). We call a graph a CCE-graph if it is the competition-common enemy graph of some digraph. We also call a graph \(G = (V, E)\) CCE-orientable if we can give an orientation \(F\) of \(G\) so that whenever \((w,u), (w,v), (u,x)\), and \((v,x)\) are in \(F\), either \((u,v)\) or \((v,u)\) is in \(F\). Bak \(et\; al. [1997]\) found a large class of graphs that are CCE-orientable and proposed an open question of finding graphs that are not CCE-orientable. In this paper, we answer their question by presenting two families of graphs that are not CCE-orientable. We also give a CCE-graph that is not CCE-orientable, which answers another question proposed by Bak \(et \;al. [1997]\). Finally, we find a new family of graphs that are CCE-orientable.

In this paper, we show the necessary and sufficient conditions for a complete graph on \(n\) vertices with a hole of size \(v\) (\(K_n \setminus K_v\)) to be decomposed into isomorphic copies of \(K_3\) with a pendant edge.