共查询到20条相似文献,搜索用时 31 毫秒
1.
Kinkar Ch. Das 《Linear algebra and its applications》2011,435(10):2420-2424
Let G = (V, E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the signless Laplacian matrix of G is Q(G) = D(G) + A(G). In [5], Cvetkovi? et al. have given the following conjecture involving the second largest signless Laplacian eigenvalue (q2) and the index (λ1) of graph G (see also Aouchiche and Hansen [1]):
2.
Vladimir Nikiforov 《Linear algebra and its applications》2006,414(1):347-360
Let G be a graph with n vertices and m edges and let μ(G) = μ1(G) ? ? ? μn(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑u∈V(G)∣d(u)-2m/n∣. We prove that
3.
Vladimir Nikiforov 《Linear algebra and its applications》2008,428(7):1492-1498
Let G be a graph of sufficiently large order n, and let the largest eigenvalue μ(G) of its adjacency matrix satisfies . Then G contains a cycle of length t for every t?n/320This condition is sharp: the complete bipartite graph T2(n) with parts of size ⌊n/2⌋ and ⌈n/2⌉ contains no odd cycles and its largest eigenvalue is equal to .This condition is stable: if μ(G) is close to and G fails to contain a cycle of length t for some t?n/321, then G resembles T2(n). 相似文献
4.
Oscar Rojo 《Linear algebra and its applications》2008,428(4):754-764
Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let Cr be the unique cycle of G. The graph G-E(Cr) is a forest of r rooted trees T1,T2,…,Tr with root vertices v1,v2,…,vr, respectively. Let
5.
A subset of vertices (resp. arcs) of a graph G is called a feedback vertex (resp. arc) set of G if its removal results in an acyclic subgraph. Let f(d,n) (fa(d,n)) denote the minimum cardinality over all feedback vertex (resp. arc) sets of the Kautz digraph K(d,n). This paper proves that for any integers d?2 and n?1
6.
Bc(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:
7.
Dongmei Zhu 《Linear algebra and its applications》2010,432(11):2764-2772
In this paper, we obtain the following upper bound for the largest Laplacian graph eigenvalue λ(G):
8.
Ding-Gong Yang 《Applied mathematics and computation》2010,215(9):3473-3481
Let Tn(A,B,α) denote the class of functions of the form:
9.
Mirko Lepovi? 《Discrete Mathematics》2007,307(6):730-738
Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that Ac=[cij] is the conjugate adjacency matrix of the graph G if cij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and cij=0 if i=j. Let PG(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if PG(λ)=PH(λ) and . Further, let Pc(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs Gi=G?i(i=1,2,…,n). If Pc(G)=Pc(H) we prove that , provided that the order of G is greater than 2. 相似文献
10.
Shaun Cooper 《Journal of Number Theory》2003,103(2):135-162
Let rk(n) denote the number of representations of an integer n as a sum of k squares. We prove that for odd primes p,
11.
The higher Randi? index Rt(G) of a simple graph G is defined as
12.
Spectral radius and Hamiltonicity of graphs 总被引:1,自引:0,他引:1
Miroslav Fiedler 《Linear algebra and its applications》2010,432(9):2170-2173
Let G be a graph of order n and μ(G) be the largest eigenvalue of its adjacency matrix. Let be the complement of G.Write Kn-1+v for the complete graph on n-1 vertices together with an isolated vertex, and Kn-1+e for the complete graph on n-1 vertices with a pendent edge.We show that:If μ(G)?n-2, then G contains a Hamiltonian path unless G=Kn-1+v; if strict inequality holds, then G contains a Hamiltonian cycle unless G=Kn-1+e.If , then G contains a Hamiltonian path unless G=Kn-1+v.If , then G contains a Hamiltonian cycle unless G=Kn-1+e. 相似文献
13.
For a simple graph G, let denote the complement of G relative to the complete graph and let PG(x)=det(xI-A(G)) where A(G) denotes the adjacency matrix of G. The complete product G∇H of two simple graphs G and H is the graph obtained from G and H by joining every vertex of G to every vertex of H. In [2]PG∇H(x) is represented in terms of PG, , PH and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials. 相似文献
14.
15.
Walks and the spectral radius of graphs 总被引:1,自引:0,他引:1
Vladimir Nikiforov 《Linear algebra and its applications》2006,418(1):257-268
Given a graph G, write μ(G) for the largest eigenvalue of its adjacency matrix, ω(G) for its clique number, and wk(G) for the number of its k-walks. We prove that the inequalities
16.
Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γk(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number irk(G). The authors prove that if an irk-set X is a k-independent set of G, then , and that for k?2, if irk(G)=1, if irk(G) is odd, and if irk(G) is even, which generalize some known results. 相似文献
17.
Mathew Cropper 《Discrete Mathematics》2006,306(16):1988-1990
Let n(G) denote the number of vertices of a graph G and let α(G) be the independence number of G, the maximum number of pairwise nonadjacent vertices of G. The Hall ratio of a graph G is defined by
18.
Let G be a graph with n vertices and m edges. Let λ1, λ2, … , λn be the eigenvalues of the adjacency matrix of G, and let μ1, μ2, … , μn be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences. 相似文献
19.
Let A=(A1,…,Am) be a sequence of finite subsets from an additive abelian group G. Let Σ?(A) denote the set of all group elements representable as a sum of ? elements from distinct terms of A, and set . Our main theorem is the following lower bound:
20.
A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersdγt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes. 相似文献