Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

On the signless Laplacian index of cacti with a given number of pendant vertices

A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.     

On extremal unicyclic molecular graphs with maximal Hosoya index

Let G be a unicyclic n-vertex graph and Z(G) be its Hosoya index, let F_n stand for the nth Fibonacci number. It is proved in this paper that Z(G)≤F_n+1+F_n−1 with the equality holding if and only if G is isomorphic to C_n, the n-vertex cycle, and that if G≠C_n then Z(G)≤F_n+1+2F_n−3 with the equality holding if and only if G=Q_n or D_n, where graph Q_n is obtained by pasting one endpoint of a 3-vertex path to a vertex of C_n−2 and D_n is obtained by pasting one endpoint of an (n−3)-vertex path to a vertex of C₄.     

Spanning Star Trees in Regular Graphs

For a subset W of vertices of an undirected graph G, let S(W) be the subgraph consisting of W, all edges incident to at least one vertex in W, and all vertices adjacent to at least one vertex in W. If S(W) is a tree containing all the vertices of G, then we call it a spanning star tree of G. In this case W forms a weakly connected but strongly acyclic dominating set for G. We prove that for every r ≥ 3, there exist r-regular n-vertex graphs that have spanning star trees, and there exist r-regular n-vertex graphs that do not have spanning star trees, for all n sufficiently large (in terms of r). Furthermore, the problem of determining whether a given regular graph has a spanning star tree is NP-complete.     

On the extremal Merrifield-Simmons index and Hosoya index of quasi-tree graphs

It is well known that the two graph invariants, “the Merrifield-Simmons index” and “the Hosoya index” are important in structural chemistry. A graph G is called a quasi-tree graph, if there exists u₀ in V(G) such that G−u₀ is a tree. In this paper, at first we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Merrifield-Simmons indices. Then we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Hosoya indices, as well as those n-vertex quasi-tree graphs with k pendent vertices having the smallest Hosoya index.     

Roman domination in regular graphs

A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑_u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γ_R(G)≤2γ(G) and defined a graph G to be Roman if γ_R(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P_3k,P_3k+2,C_3k,C_3k+2 for k≥1, K_m,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

The inducibility of graphs

We investigate the maximum number of ways in which a k-vertex graph G can appear as an induced subgraph of an n-vertex graph, for n ≥ k. When this number is expressed as a fraction of all k-vertex induced subgraphs, it tends to a definite limit as n → ∞. This limit, which we call the inducibility of G, is an effectively computable invariant of G. We examine the elementary properties of this invariant: its relationship to various operations on graphs, its maximum and minimum values, and its value for some particular graphs.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

A new family of expansive graphs

An affine graph is a pair (G,σ) where G is a graph and σ is an automorphism assigning to each vertex of G one of its neighbors. On one hand, we obtain a structural decomposition of any affine graph (G,σ) in terms of the orbits of σ. On the other hand, we establish a relation between certain colorings of a graph G and the intersection graph of its cliques K(G). By using the results we construct new examples of expansive graphs. The expansive graphs were introduced by Neumann-Lara in 1981 as a stronger notion of the K-divergent graphs. A graph G is K-divergent if the sequence |V(Kⁿ(G))| tends to infinity with n, where Kⁿ⁺¹(G) is defined by Kⁿ⁺¹(G)=K(Kⁿ(G)) for n?1. In particular, our constructions show that for any k?2, the complement of the Cartesian product C^k, where C is the cycle of length 2k+1, is K-divergent.     

Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity

In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=K_k(K₁+K_n−k−1), the join of K_k, the complete graph on k vertices, with the disjoint union of K₁ and K_n−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Packing edge-disjoint cycles in graphs and the cyclomatic number

For a graph G let μ(G) denote the cyclomatic number and let ν(G) denote the maximum number of edge-disjoint cycles of G.We prove that for every k≥0 there is a finite set P(k) such that every 2-connected graph G for which μ(G)−ν(G)=k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k≤2 exactly.     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

On time-relaxed broadcasting networks

Given a communication network (modelled as a graph), a message is transmitted to at one vertex transmits to all other vertices in such a way that each message transmission takes one time unit and each vertex participates in at most one transmission to its neighbor per time step. We call this process broadcasting. For t≥0, let B_t(n) be the number of edges in the sparsest possible graph on n vertices in which broadcasting can be accomplished in ⌈log₂n⌉+t steps regardless of the originator. Shastri [A. Shastri, Time-relaxed broadcasting in communication networks, Discrete Applied mathematics 83 (1998) 263-278] conjectured that B₁(22)=24 and B₂(n)=n+1 for 25≤n≤29. In this paper, we show that B₁(22)=24, B₂(n)=n for 25≤n≤28 and 37≤n≤44, B₂(n)≤n+1 for 45≤n≤49, B₂(n)≤n+4 for 50≤n≤56, and B₃(n)=n for 55≤n≤64.     

Bandwidth of the corona of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(u)-f(v)|:uv∈E(G)} taken over all injective integer numberings f of G. The corona of two graphs G and H, written as G°H, is the graph obtained by taking one copy of G and |V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the bandwidth of the corona of two graphs. For a graph G, we denote the connectivity of G by κ(G). Let G be a graph on n vertices with B(G)=κ(G)=k?2 and let H be a graph of order m. Let c,p and q be three integers satisfying 1?c?k-1 and . We define h_i=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1 for i=1,2,…,k and b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}. Then, among other results, we prove that