The path spectrum, \(\operatorname{sp}(G)\), of a graph \(G\) is the set of all lengths of maximal paths in \(G\). The path spectrum is continuous if \(\operatorname{sp}(G) = \{\ell, \ell1, \dots, \ell\}\) for some \(\ell \leq m\). A graph whose path spectrum consists of a single element is called scent and is by definition continuous. In this paper, we determine when a \(\{K_{1, 3}, S\}\)-free graph has a continuous path spectrum where \(S\) is one of \(C_3, P_4, P_5, P_6, Z_1, Z_2, Z_3, N, B\), or \(W\).

A graph \(G\) is \((p, q, r)\)-choosable if for every list assignment \(L\) with \(|L(v)| \geq p\) for each \(v \in V(G)\) and \(|L(u) \cap L(v)| < p – r\) whenever \(u, v\) are adjacent vertices, \(G\) is \(q\)-tuple \(L\)-colorable. We give an alternative proof of \((4t, t, 3t)\)-choosability for the planar graphs and construct a triangle-free planar graph on \(119\) vertices which is not \((3, 1, 1)\)-choosable (and so neither \(3\)-choosable). We also propose some problems.

We study the behaviour of two domination parameters: the split domination number \(\gamma_s(G)\) of a graph \(G\) and the maximal domination number \(\gamma_m(G)\) of \(G\) after the deletion of an edge from \(G\). The motivation of these problems comes from [2]. In [6] Vizing gave an upper bound for the size of a graph with a given domination number. Inspired by [5] we formulate Vizing type relation between \(|E(G)|, |V(G)|, \Delta(G)\) and \(\delta(G)\), where \(\Delta(G)\) (\(\delta(G)\)) denotes the maximum (minimum) degree of \(G\).

A \(2\)-factor \(F\) of a bipartite graph \(G = (A, B; E)\), \(|A| = |B| = n\), is small if \(F\) comprises \(\lfloor \frac{n}{2}\rfloor\) cycles. A set \(\mathfrak{F}\) of small edge-disjoint \(2\)-factors of \(G\) is maximal if \(G – \mathfrak{F}\) does not contain a small \(2\)-factor. We study the spectrum of maximal sets of small \(2\)-factors.

The linear vertex-arboricity of a graph \(G\) is defined as the minimum number of subsets into which the vertex-set \(V(G)\) can be partitioned so that every subset induces a linear forest. In this paper, we give the upper and lower bounds for the sum and product of linear vertex-arboricity with independence number and with clique cover number, respectively. All of these bounds are sharp.

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.