Search

Any line graph L(G), the vertices correspond to the edges of G(V, E) and two vertices in L(G) are adjacent if and only if the corresponding edges in G are adjacent". "If there are vertices u, v in x, y such that dg, G -[G,-] for any pair of vertices S, G in G, then the set G of vertices of f is said to be a double geodetic set of The lowest cardinality of a double geodetic set is represented by the double geodetic number. In this study, we determine double geodetic number of several line graphs. [ABSTRACT FROM AUTHOR]

For a simple graph $G(V,E)$ with $n$ vertices, $m$ edges, vertex set $V(G)=\{v_1, v_2, \dots, v_n\}$ and edge set $E(G)=\{e_1, e_2,\dots, e_m\}$, the adjacency matrix $A=(a_{ij})$ of $G$ is a $(0, 1)$-square matrix of order $n$ whose $(i,j)$-entry is equal to 1 if $v_i$ is adjacent to $v_j$ and equal to 0, otherwise. Let $D(G)={diag}(d_1, d_2, \dots, d_n)$ be the diagonal matrix associated to $G$, where $d_i=\deg(v_i),$ for all $i\in \{1,2,\dots,n\}$. The matrices $L(G)=D(G)-A(G)$ and $Q(G)=D(G)+A(G)$ are respectively called the Laplacian and the signless Laplacian matrices and their spectra (eigenvalues) are respectively called the Laplacian spectrum ($L$-spectrum) and the signless Laplacian spectrum ($Q$-spectrum) of the graph $G$. If $0=\mu_n\leq\mu_{n-1}\leq\cdots\leq\mu_1$ are the Laplacian eigenvalues of $G$, Brouwer conjectured that the sum of $k$ largest Laplacian eigenvalues $S_{k}(G)$ satisfies $S_{k}(G)=\sum\limits_{i=1}^{k}\mu_i\leq m+{k+1 \choose 2}$ and this conjecture is still open. If $q_1,q_2, \dots, q_n$ are the signless Laplacian eigenvalues of $G$, for $1\leq k\leq n$, let $S^{+}_{k}(G)=\sum_{i=1}^{k}q_i$ be the sum of $k$ largest signless Laplacian eigenvalues of $G$. Analogous to Brouwer's conjecture, Ashraf et al. conjectured that $S^{+}_{k}(G)\leq m+{k+1 \choose 2}$, for all $1\leq k\leq n$. This conjecture has been verified in affirmative for some classes of graphs. We obtain the upper bounds for $S^{+}_{k}(G)$ in terms of the clique number $\omega$, the vertex covering number $\tau$ and the diameter of the graph $G$. Finally, we show that the conjecture holds for large families of graphs.

Let G be a simple connected graph with n vertices and m edges. Let W (G) = (G , w) be the weighted graph corresponding to G. Let λ 1 , λ 2 , ... , λ n be the eigenvalues of the adjacency matrix A (W (G)) of the weighted graph W (G). The energy E (W (G)) of a weighted graph W (G) is defined as the sum of absolute value of the eigenvalues of W (G). In this paper, we obtain upper bounds for the energy E (W (G)) , in terms of the sum of the squares of weights of the edges, the maximum weight, the maximum degree d 1 , the second maximum degree d 2 and the vertex covering number τ of the underlying graph G. As applications to these upper bounds we obtain some upper bounds for the energy (adjacency energy), the extended graph energy, the Randić energy and the signed energy of the connected graph G. We also obtain some new families of weighted graphs where the energy increases with increase in weights of the edges. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with n vertices, m edges and having adjacency eigenvalues λ1, λ2, ..., λn. The energy E(G) of the graph G is defined as E(G) = ∑i=1n∣λi∣. In this paper, we obtain the upper bounds for the energy E(G) in terms of the vertex covering number τ, the clique number ω, the number of edges m, maximum vertex degree d1 and second maximum vertex degree d2 of the connected graph G. These upper bounds improve some of the recently known upper bounds. [ABSTRACT FROM AUTHOR]

For a simple graph G(V,E)with nvertices, medges, vertex set V(G) = {v1,v2, . . . , vn}and edge set E(G) = {e1,e2, . . . , em}, the adjacency matrix A= (aij )of Gis a (0, 1)-square matrixof order nwhose (i,j)-entry is equal to 1 if viis adjacent to vjand equal to 0, otherwise. LetD(G) = diag(d1,d2, . . . , dn)be the diagonal matrix associated to G, where di=deg(vi), for all i∈{1, 2, . . . , n}. The matrices L(G) = D(G)−A(G)and Q(G) = D(G) + A(G)are respectively calledthe Laplacian and the signless Laplacian matrices and their spectra (eigenvalues) are respectivelycalled the Laplacian spectrum (L-spectrum) and the signless Laplacian spectrum (Q-spectrum) ofthe graph G. If 0 =µn≤µn−1≤ · ·· ≤ µ1are the Laplacian eigenvalues of G, Brouwer conjecturedthat the sum of klargest Laplacian eigenvalues Sk(G)satisfies Sk(G) = k∑i=1µi≤m+(k+12)and thisconjecture is still open. If q1,q2, . . . , qnare the signless Laplacian eigenvalues of G, for 1 ≤k≤n,let S+k(G) = ∑ki=1qibe the sum of klargest signless Laplacian eigenvalues of G. Analogous toBrouwer’s conjecture, Ashraf et al. conjectured that S+k(G)≤m+(k+12), for all 1 ≤k≤n. Thisconjecture has been verified in affirmative for some classes of graphs. We obtain the upper boundsfor S+k(G)in terms of the clique number ω, the vertex covering number τand the diameter of thegraph G. Finally, we show that the conjecture holds for large families of graphs. [ABSTRACT FROM AUTHOR]

For a simple graph G with n vertices and m edges having adjacency eigenvalues λ1;λ2,...,λn, the energy E (G) of G is defined as E (G) = Σni=1 |λi|. We obtain the upper bounds for E (G) in terms of the vertex covering number t, the number of edges m, maximum vertex degree d1 and second maximum vertex degree d2 of the connected graph G. These upper bounds improve some recently known upper bounds for E (G). Further, these upper bounds for E (G) imply a natural extension to other energies like distance energy and Randic energy associated to a connected graph G. [ABSTRACT FROM AUTHOR]

For a simple graph G with n vertices and m edges having Laplacian eigenvalues μ 1 ( G ) ≥ μ 2 ( G ) ≥ ⋯ ≥ μ n ( G ) , let S k ( G ) be the sum of k largest Laplacian eigenvalues of G . In this note, we prove that if G is a connected graph of order n ≥ 2 with m edges having clique number ω and vertex covering number τ , then S k ( G ) ≤ k ( τ + 1 ) + m − ω ( ω − 1 ) 2 , with equality if k ≤ ω − 1 and G is the graph obtained by joining n − ω pendant vertices with one of the vertices in K ω . Our work improves a recent work of Ganie et al. [ABSTRACT FROM AUTHOR]

We study the problem of using mobile guards to defend the vertices of a graph against a single attack on its vertices. A vertex cover of a graph is a set such that for each edge , at least one of or is in . The minimum cardinality of a vertex cover is termed the vertex covering number and it is denoted by . In this context, we introduce a new protection strategy called the secure vertex cover SVC problem, where the guards are placed at the vertices of a graph, in order to protect the graph against a single attack on its vertices. We are concerned with the protection of against a single attack, using at most one guard per vertex and require the set of guarded vertices to be a vertex cover. In addition, if any guard moves along an edge to deal with an attack to an unguarded vertex, then the resulting placement of guards must also form a vertex cover. Formally, this protection strategy defends the vertices of a graph against a single attack and simultaneously protects the edges. We define a SVC to be a set such that is a vertex cover and for each , there exists a such that is a vertex cover. The minimum cardinality of an SVC is called the secure vertex covering number and it is denoted by . In this paper, a few properties of SVC of a graph are studied and specific values of for few classes of well-known graphs are evaluated. [ABSTRACT FROM AUTHOR]

Let G be a graph. If u, v G V(G), a u Ε v geodesic of G is the shortest path between u and v. The closed interval I[u, v] consists of all vertices lying in some u - v geodesic of G. For S ⊆ V(G) the set I[S] is the union of all sets I[u, v] for u, v Ε S. A set S is a geodetic set of G if I (S) = V (G). The cardinality of a minimum geodetic set of G is the geodetic number of G, denoted by g(G). In this paper, we study the nonsplit geodetic number of a graph gns(G). The set S ⊆ V (G) is a nonsplit geodetic set in G if S is a geodetic set and ‹V(G) -- S› is connected, nonsplit geodetic number gns(G) of G is the minimum cardinality of a nonsplit geodetic set of G. We investigate the relationship between nonsplit geodetic number and geodetic number. We also obtain the nonsplit geodetic number in the cartesian product of graphs. [ABSTRACT FROM AUTHOR]

LetGbe a graph of order n with no isolated vertex. A vertex covering of the graphGis a set of vertices such that every edge of the graph is incident to atleast one vertex of the set. LetC(G, i) be the family of vertex covering sets inGwith cardinality ‘i’ and letc(G, i) = |C(G, i) |. The polynomialis called the vertex cover polynomial ofG. In this paper, we obtain some properties of vertex cover polynomials of. Also, we derive the reduction formula to calculate the vertex covering polynomials of. [ABSTRACT FROM PUBLISHER]

A set S ⊆ V [L(G)] is a split geodetic set of L(G), if S is a geodetic set and V - S is disconnected. The split geodetic number of a line graph L(G), denoted by gs[L(G)] is the minimum cardinality of a split geodetic set of L(G). In this paper we obtain the split geodetic number of line graph of any graph. Also obtain many bounds on split geodetic number in terms of elements of G and covering number of G. We also investigate the relationship between split geodetic number and geodetic number. [ABSTRACT FROM AUTHOR]

We consider the concept of fractional vertex covering function of a graph. In this paper, we study the effect of removing a vertex from the graph on fractional vertex covering number of the graph. In particular, We prove that iffis a minimum fractional vertex covering function on G andf(v) ≠ 0 then the fractional vertex covering number of the graph decreases when the vertex v is removed from the graph. [ABSTRACT FROM PUBLISHER]

Abstract: Let G be a connected (di)graph. A vertex is said to strongly resolve a pair of vertices of G if there exists some shortest – path containing or some shortest – path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied. [Copyright &y& Elsevier]

Graph invariants are the properties of graphs that do not change under graph isomorphisms, the independent set decision problem, vertex covering problem, and matching number problem are known to be NP-Hard, and hence it is not believed that there are efficient algorithms for solving them. In this paper, the graph invariants matching number, vertex covering number, and independence number for the zero-divisor graph over the rings Z p k and Z p k q r are determined in terms of the sets S p i and S p i q j respectively. Accordingly, a formula in terms of p , q , k , and r, with n = p k , n = p k q r is provided. [ABSTRACT FROM AUTHOR]