共查询到10条相似文献,搜索用时 109 毫秒
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.
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
Baogen Xu 《Discrete Applied Mathematics》2006,154(10):1541-1546
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.
Jakob Jonsson 《Journal of Combinatorial Theory, Series A》2008,115(8):1504-1526
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.
Ngoc Gioan Jean Pagnon 《Indagationes Mathematicae》2004,15(1):101-114
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 X ∩ X 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.
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, .