共查询到20条相似文献,搜索用时 31 毫秒
1.
Saieed Akbari Alireza Alipour Javad Ebrahimi Boroojeni Mirhamed Mirjalalieh Shirazi 《Linear algebra and its applications》2007,422(1):341-347
Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that . 相似文献
2.
Robert Berke 《Discrete Mathematics》2010,310(3):561-569
We define by minc∑{u,v}∈E(G)|c(u)−c(v)| the min-costMC(G) of a graph G, where the minimum is taken over all proper colorings c. The min-cost-chromatic numberχM(G) is then defined to be the (smallest) number of colors k for which there exists a proper k-coloring c attaining MC(G). We give constructions of graphs G where χ(G) is arbitrarily smaller than χM(G). On the other hand, we prove that for every 3-regular graph G′, χM(G′)≤4 and for every 4-regular line graph G″, χM(G″)≤5. Moreover, we show that the decision problem whether χM(G)=k is -hard for k≥3. 相似文献
3.
A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are ω,n0>0 such that if G is a Dirac graph on n≥n0 vertices, d is an arbitrary integer with 3≤d≤ωn/2 and S is an arbitrary subset of the vertices of G with 2≤|S|=k≤ωn/d, then for every sequence di of integers with 3≤di≤d,1≤i≤k−1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a1,a2,…,ak, such that the vertices of S are visited in this order on C and we have
4.
For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ1 is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that . 相似文献
5.
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. 相似文献
6.
7.
Edith Hemaspaandra Lane A. Hemaspaandra Stanis?aw P. Radziszowski 《Discrete Applied Mathematics》2007,155(2):103-118
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:
- (1)
- , , , and .
- (2)
- For all k?2, and .
- (3)
- For all k?2, .
- (4)
- .
- (5)
- For all k?2, .
8.
The Hadwiger number η(G) of a graph G is the largest integer h such that the complete graph on h nodes Kh is a minor of G. Equivalently, η(G) is the largest integer such that any graph on at most η(G) nodes is a minor of G. The Hadwiger's conjecture states that for any graph G, η(G)?χ(G), where χ(G) is the chromatic number of G. It is well-known that for any connected undirected graph G, there exists a unique prime factorization with respect to Cartesian graph products. If the unique prime factorization of G is given as G1□G2□?□Gk, where each Gi is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently.In this paper, we study the Hadwiger's conjecture for graphs in terms of their prime factorization. We show that the Hadwiger's conjecture is true for a graph G if the product dimension of G is at least . In fact, it is enough for G to have a connected graph M as a minor whose product dimension is at least , for G to satisfy the Hadwiger's conjecture. We show also that if a graph G is isomorphic to Fd for some F, then η(G)?χ(G)⌊(d-1)/2⌋, and thus G satisfies the Hadwiger's conjecture when d?3. For sufficiently large d, our lower bound is exponentially higher than what is implied by the Hadwiger's conjecture.Our approach also yields (almost) sharp lower bounds for the Hadwiger number of well-known graph products like d-dimensional hypercubes, Hamming graphs and the d-dimensional grids. In particular, we show that for the d-dimensional hypercube Hd, . We also derive similar bounds for Gd for almost all G with n nodes and at least edges. 相似文献
9.
Zhao Zhang 《Discrete Mathematics》2008,308(20):4560-4569
An edge set S of a connected graph G is a k-extra edge cut, if G-S is no longer connected, and each component of G-S has at least k vertices. The cardinality of a minimum k-extra edge cut, denoted by λk(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γk(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write βk(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with is said to be γk-optimal.In this paper, we first prove that λk(G)=γk(G) if G is a regular graph with girth g?k/2. Then, we show that except for K3,3 and K4, a 3-regular vertex/edge transitive graph is γk-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d?6ek(G)/k is γk-optimal, where ek(G) is the maximum number of edges in a subgraph of G with order k. 相似文献
10.
Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, Ck(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ∗(G), is the maximum integer k such that G is w∗-connected for 1≤w≤k if G is 1∗-connected.Let x be a vertex in G and let U={y1,y2,…,yk} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, Fk(x,U), is a set of internally-disjoint paths {P1,P2,…,Pk} such that Pi is a path connecting x to yi for 1≤i≤k and . A graph G is k∗-fan-connected (or -connected) if there exists a spanning Fk(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k∗-pipeline-connected. 相似文献
11.
Wang Qin 《Discrete Mathematics》2005,294(3):303-309
A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K1,3. The kth power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and Tr, r?2, where Tr is the graph with 4r vertices ui,vi,xi,yi, 1?i?r, such that for each i with 1?i?r, {ui,vi,xi,yi} is a clique of Tr and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K4×K2, and . 相似文献
12.
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
13.
Mordecai J. Golin 《Discrete Mathematics》2010,310(4):792-803
Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s1,i±s2,…,i±sk where all the operations are . We give a closed formula for the asymptotic limit as a function of s1,s2,…,sk. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting si, di and ei be arbitrary integers, and examining
14.
Alewyn P. Burger 《Discrete Mathematics》2009,309(8):2473-2036
The relationship ρL(G)≤ρ(G)≤γ(G) between the lower packing number ρL(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants aθ, bθ, cθ and dθ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible. 相似文献
15.
A graph G is (k+1)-critical if it is not k-colourable but G−e is k-colourable for any edge e∈E(G). In this paper we show that for any integers k≥3 and l≥5 there exists a constant c=c(k,l)>0, such that for all , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn2 edges. 相似文献
16.
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]):
17.
Equitable colorings of Kronecker products of graphs 总被引:1,自引:0,他引:1
Wu-Hsiung Lin 《Discrete Applied Mathematics》2010,158(16):1816-1826
For a positive integer k, a graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) whenever xy∈E(G) and ||f−1(i)|−|f−1(j)||≤1 for 1≤i<j≤k. The equitable chromatic number of a graph G, denoted by χ=(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by , is the minimum t such that G is equitably k-colorable for k≥t. The current paper studies equitable chromatic numbers of Kronecker products of graphs. In particular, we give exact values or upper bounds on χ=(G×H) and when G and H are complete graphs, bipartite graphs, paths or cycles. 相似文献
18.
Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal
For a connected graph G=(V,E), an edge set S⊂E is a k-restricted-edge-cut, if G-S is disconnected and every component of G-S has at least k vertices. The k-restricted-edge-connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted-edge-cut. The k-isoperimetric-edge-connectivity is defined as , where is the set of edges with one end in U and the other end in . In this note, we give some degree conditions for a graph to have optimal λk and/or γk. 相似文献
19.
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