Rainbowness of cubic plane graphs

The rainbowness, rb(G), of a connected plane graph G is the minimum number k such that any colouring of vertices of the graph G using at least k colours involves a face all vertices of which receive distinct colours. For a connected cubic plane graph G we prove that

     

The independence polynomial of rooted products of graphs

A stable (or independent) set in a graph is a set of pairwise nonadjacent vertices thereof. The stability numberα(G) is the maximum size of stable sets in a graph G. The independence polynomial of G is

     

Walks and the spectral radius of graphs

Given a graph G, write μ(G) for the largest eigenvalue of its adjacency matrix, ω(G) for its clique number, and w_k(G) for the number of its k-walks. We prove that the inequalities

     

Eigenvalues and forbidden subgraphs I

Suppose a graph G have n vertices, m edges, and t triangles. Letting λ_n(G) be the largest eigenvalue of the Laplacian of G and μ_n(G) be the smallest eigenvalue of its adjacency matrix, we prove that

     

Characterization of graphs having extremal Randi? indices

The higher Randi? index R_t(G) of a simple graph G is defined as

     

Tight bounds for eternal dominating sets in graphs

The eternal domination number of a graph is the number of guards needed at vertices of the graph to defend the graph against any sequence of attacks at vertices. We consider the model in which at most one guard can move per attack and a guard can move across at most one edge to defend an attack. We prove that there are graphs G for which , where γ_∞(G) is the eternal domination number of G and α(G) is the independence number of G. This matches the upper bound proved by Klostermeyer and MacGillivray.     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.     

On upper bounds for Laplacian graph eigenvalues

In this paper, we obtain the following upper bound for the largest Laplacian graph eigenvalue λ(G):

     

The intersection of all maximum stable sets of a tree and its pendant vertices

A stable set in a graph G is a set of mutually non-adjacent vertices, α(G) is the size of a maximum stable set of G, and is the intersection of all its maximum stable sets. It is known that if G is a connected graph of order n≥2 with 2α(G)>n, then , [V.E. Levit, E. Mandrescu, Combinatorial properties of the family of maximum stable sets of a graph, Discrete Applied Mathematics 117 (2002) 149-161; E. Boros, M.C. Golumbic, V.E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Applied Mathematics 124 (2002) 17-25]. When we restrict ourselves to the class of trees, we add some structural properties to this statement. Our main finding is the theorem claiming that if T is a tree of order n≥2, with 2α(T)>n, then at least two pendant vertices an even distance apart belong to .     

Eigenvalues and degree deviation in graphs

Let G be a graph with n vertices and m edges and let μ(G) = μ₁(G) ? ? ? μ_n(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑_u∈V(G)∣d(u)-2m/n∣. We prove that

     

Cyclic bandwidth with an edge added

B_c(G) denotes the cyclic bandwidth of graph G. In this paper, we obtain the maximum cyclic bandwidth of graphs of order p with adding an edge as follows:

     

Turán's theorem for pseudo-random graphs

The generalized Turán number ex(G,H) of two graphs G and H is the maximum number of edges in a subgraph of G not containing H. When G is the complete graph Km on m vertices, the value of ex(Km,H) is , where o(1)→0 as m→∞, by the Erd?s-Stone-Simonovits theorem.In this paper we give an analogous result for triangle-free graphs H and pseudo-random graphs G. Our concept of pseudo-randomness is inspired by the jumbled graphs introduced by Thomason [A. Thomason, Pseudorandom graphs, in: Random Graphs '85, Poznań, 1985, North-Holland, Amsterdam, 1987, pp. 307-331. MR 89d:05158]. A graph G is (q,β)-bi-jumbled if

     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

The largest eigenvalue of unicyclic graphs

Let G be a simple graph. Let λ₁(G) and μ₁(G) denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let Δ denote the largest vertex degree. If G has just one cycle, then

     

Inverse degree and edge-connectivity

Let G be a connected graph with vertex set V(G), order n=|V(G)|, minimum degree δ and edge-connectivity λ. Define the inverse degree of G as , where d(v) denotes the degree of the vertex v. We show that if

     

Independence polynomials of k-tree related graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let α(G) denote the cardinality of a maximum independent set and f_s(G) for 0≤s≤α(G) denote the number of independent sets of s vertices. The independence polynomial defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients f_s(T) for trees T with n vertices: for s≥2. We generalize this result to bounds for a very large class of graphs, maximal k-degenerate graphs, a class which includes all k-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of k-tree related graphs. Our main theorems generalize several related results known before.