Font Size: a A A

Research On Some Parameters Of Graphs

Posted on:2016-09-05Degree:DoctorType:Dissertation
Country:ChinaCandidate:W J NingFull Text:PDF
GTID:1220330503456261Subject:Mathematics
Abstract/Summary:PDF Full Text Request
Let G be a simple undirected graph of order n, A(G) be the adjacency matrix of G and D(G) = diag(d1, d2, · · ·, dn) be the diagonal matrix of vertex degrees. Then the signless Laplacian matrix of G is Q(G) = A(G) + D(G). The signless Laplacian spectral radius q1(G) of G is the largest eigenvalue of Q(G). Given a graph G =(V, E)with no isolated vertex, a total dominating set S of G is a locating-total dominating set if for every pair of distinct vertices u and v in V- S, we have N(u) ∩ S N(v) ∩ S,where N(u) = {w | uw ∈ E}; S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, we have N[u] ∩ S N[v] ∩ S, where N[u] =N(u) ∪ {u}. The locating-total domination number γL t(G)( or the differentiating-total domination number γD t(G)), is the minimum cardinality of a locating-total dominating set( or a differentiating-total dominating set) of G. A subset S of V is a 2-dominating set of G if every vertex of G not in S is adjacent to at least two vertices in S. The2-domination number γ2(G), is the minimum size of a 2-dominating set in G. The annihilation number a(G), is the largest integer k such that the sum of the first k terms of the nondecreasing degree sequence of G is at most the number of edges in G.In Chapter 3, we investigate lower and upper bounds for the signless Laplacian spectral radius of a graph. Given an irregular graph G, we give a lower bound for2?- q1(G) in terms of the diameter d and the order n. Lower bounds for q1(G)-4mnare also given in terms of the maximum degree ?, the minimum degree δ and the order n. Finally, we obtain some lower bounds of 2?- q1(G) using the maximum degree ?,the minimum degree δ, the connectivity κ, the order n and the size m.In Chapter 4, we give lower and upper bounds for the differentiating-total domination number of a tree in terms of its order n, the diameter d and the number l of leaves;we also characterize trees achieving these bounds. Also, we give the extreme values of the locating and differentiating-total domination numbers of a unicyclic graph in terms of its order n, the number s of support vertices, the number s1 of strong support verticesand the number l of leaves. The extreme graphs are also characterized.In Chapter 5, we study the relation between the locating-total domination number and the annihilation number of a tree. Finally, we give an upper bound of the2-domination number of a unicyclic graph in terms of its annihilation number, partially solving a conjecture on the 2-domination number and the annihilation number of a graph.
Keywords/Search Tags:signless Laplacian spectral radius, locating-total domination, differentiating-total domination, 2-domination number, annihilation number
PDF Full Text Request
Related items