首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 109 毫秒
1.
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.
Zemin Jin 《Discrete Mathematics》2008,308(23):5864-5870
Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.  相似文献   

3.
Let G=(X,Y) be a bipartite graph and define . Moon and Moser [J. Moon, L. Moser, On Hamiltonian bipartite graphs, Israel J. Math. 1 (1963) 163-165. MR 28 # 4540] showed that if G is a bipartite graph on 2n vertices such that , then G is hamiltonian, sharpening a classical result of Ore [O. Ore, A note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55] for bipartite graphs. Here we prove that if G is a bipartite graph on 2n vertices such that , then G contains k edge-disjoint hamiltonian cycles. This extends the result of Moon and Moser and a result of R. Faudree et al. [R. Faudree, C. Rousseau, R. Schelp, Edge-disjoint Hamiltonian cycles, Graph Theory Appl. Algorithms Comput. Sci. (1984) 231-249].  相似文献   

4.
5.
Two classes of edge domination in graphs   总被引:2,自引:0,他引:2  
Let (, resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that and hold for any graph G of order n(n?4), and pose several open problems and conjectures.  相似文献   

6.
7.
Building on work by Bouc and by Shareshian and Wachs, we provide a toolbox of long exact sequences for the reduced simplicial homology of the matching complex Mn, which is the simplicial complex of matchings in the complete graph Kn. Combining these sequences in different ways, we prove several results about the 3-torsion part of the homology of Mn. First, we demonstrate that there is nonvanishing 3-torsion in whenever , where . By results due to Bouc and to Shareshian and Wachs, is a nontrivial elementary 3-group for almost all n and the bottom nonvanishing homology group of Mn for all n≠2. Second, we prove that is a nontrivial 3-group whenever . Third, for each k?0, we show that there is a polynomial fk(r) of degree 3k such that the dimension of , viewed as a vector space over Z3, is at most fk(r) for all r?k+2.  相似文献   

8.
In the article [Spa1], N. Spaltenstein has established a bijection between the irreducible components of χ, the space of full flags fixed by a nilpotent element χ ? M(n, k), where k is an algebraically closed field, and the standard tableaux associated to the Young diagram of χ. In this present work we determine, when χ is of hook type, for each irreducible component X of χ, the unique Schubert cell X of the full flag manifold = (V) (where V is vector space of dimension n over k), such that XX is a dense subspace in X. This result will allow us to optimize the computation of χ and when k = is the complex field, to see that the graph resolution of the partition (2, 1, …, 1) of n is related to the Dynkin diagram of sl(n, ).  相似文献   

9.
Cospectral graphs and the generalized adjacency matrix   总被引:1,自引:0,他引:1  
Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value of y. We call such graphs -cospectral. It follows that is a rational number, and we prove existence of a pair of -cospectral graphs for every rational . In addition, we generate by computer all -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of -cospectral graphs for all rational , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of , and by computer we find all such pairs of -cospectral graphs on at most eleven vertices.  相似文献   

10.
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, .
For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn(G) and ern(G), and give an example of a family {Gn}n?4 of graphs on n vertices for which vrn(Gn)<vrn(Gn). For every k?2 and n?1, we show that there exists a collection of k graphs on (2k-1+1)n+k vertices with 2n 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号