首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 218 毫秒
1.
Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ l (G + K n ) = ρ(G + K n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ l (G) = ρ(G). Particularly, we determine that , where K 2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.  相似文献   

2.
The signed total domination number of a graph is a certain variant of the domination number. If is a vertex of a graph G, then N() is its oper neighbourhood, i.e. the set of all vertices adjacent to in G. A mapping f: V(G)-1, 1, where V(G) is the vertex set of G, is called a signed total dominating function (STDF) on G, if for each V(G). The minimum of values , taken over all STDF's of G, is called the signed total domination number of G and denoted by st(G). A theorem stating lower bounds for st(G) is stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on n-side prisms. At the end it is proved that st(G) is not bounded from below in general.  相似文献   

3.
Let γ pr (G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ pr (Gv) < γ pr (G). We call these graphs γ pr -critical. In this paper, we present a method of constructing γ pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ pr -critical graph is at most and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. Xinmin Hou: Research supported by NNSF of China (No.10701068 and No.10671191).  相似文献   

4.
We present results on total domination in a partitioned graph G = (V, E). Let γ t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ t (G; V i ) be the cardinality of a smallest subset of V such that every vertex of V i has a neighbour in it and define the following
We summarize known bounds on γ t (G) and for graphs with all degrees at least δ we derive the following bounds for f t (G; k) and g t (G; k).
(i)  For δ ≥ 2 and k ≥ 3 we prove f t (G; k) ≤ 11|V|/7 and this inequality is best possible.
(ii)  for δ ≥ 3 we prove that f t (G; 2) ≤ (5/4 − 1/372)|V|. That inequality may not be best possible, but we conjecture that f t (G; 2) ≤ 7|V|/6 is.
(iii)  for δ ≥ 3 we prove f t (G; k) ≤  3|V|/2 and this inequality is best possible.
(iv)  for δ ≥ 3 the inequality g t (G; k) ≤ 3|V|/4 holds and is best possible.
  相似文献   

5.
The closed neighborhood NG[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each eE(G), then f is called a signed edge dominating function of G. The signed edge domination number γs(G) of G is defined as . Recently, Xu proved that γs(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γs(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γs(G) = 1 − k, 2 − k. A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia. Send offprint requests to: Abdollah Khodkar.  相似文献   

6.
The main purpose of this paper is to introduce several measures determined by a given finite directed graph. To construct σ-algebras for those measures, we consider several algebraic structures induced by G; (i) the free semigroupoid of the shadowed graph (ii) the graph groupoid of G, (iii) the disgram set and (iv) the reduced diagram set . The graph measures determined by (i) is the energy measure measuing how much energy we spent when we have some movements on G. The graph measures determined by (iii) is the diagram measure measuring how long we moved consequently from the starting positions (which are vertices) of some movements on G. The graph measures and determined by (ii) and (iv) are the (graph) groupoid measure and the (quotient-)groupoid measure, respectively. We show that above graph measurings are invariants on shadowed graphs of finite directed graphs. Also, we will consider the reduced diagram measure theory on graphs. In the final chapter, we will show that if two finite directed graphs G 1 and G 2 are graph-isomorphic, then the von Neumann algebras L (μ 1) and L (μ 2) are *-isomorphic, where μ 1 and μ 2 are the same kind of our graph measures of G 1 and G 2, respectively. Received: December 7, 2006. Revised: August 3, 2007. Accepted: August 18, 2007.  相似文献   

7.
Let {G n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G n | = n. Denote by p t (v, v) the return probability after t steps of the non-backtracking random walk on G n . We show that if p t (v, v) has quasi-random properties, then critical bond-percolation on G n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G n | = n. Denote by p t (v, v) the return probability after t steps of the non-backtracking random walk on G n . We show that if p t (v, v) has quasi-random properties, then critical bond-percolation on G n behaves as it would on a random graph. More precisely, if
lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ¥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}  相似文献   

8.
Maximal Energy Bipartite Graphs   总被引:1,自引:0,他引:1  
 Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then
must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy bipartite graphs. Received: December 1, 2000 Final version received: August 28, 2001 RID="*" ID="*" The author thanks the Swedish Natural Science Research Council (NFR) – grant M12342-300 – for its support. Acknowledgments. The authors would like to thank Ivan Gutman for encouraging them to write this paper, and for helpful discussions on this topic. They also would like to thank Edwin van Dam for his reference concerning connected bipartite regular graphs with four eigenvalues.  相似文献   

9.
The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G 1 and G 2 with η(G 1) = h and η(G 2) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following:
1.  Let G be a connected graph. Let be the (unique) prime factorization of G. Then G satisfies Hadwiger’s conjecture if k ≥ 2 log log χ(G) + c′, where c′ is a constant. This improves the 2 log χ(G) + 3 bound in [2].
2.  Let G 1 and G 2 be two graphs such that χ(G 1) ≥ χ(G 2) ≥ c log1.5(χ(G 1)), where c is a constant. Then satisfies Hadwiger’s conjecture.
3.  Hadwiger’s conjecture is true for G d (Cartesian product of G taken d times) for every graph G and every d ≥ 2. This settles a question by Chandran and Sivadasan [2]. (They had shown that the Hadiwger’s conjecture is true for G d if d ≥ 3).
Alexandr Kostochka: Research of this author is supported in part by NSF grant DMS-0650784 and grant 06-01-00694 of the Russian Foundation for Basic Research.  相似文献   

10.
We prove that the identity
holds for all directed graphs G and H. Similar bounds for the usual chromatic number seem to be much harder to obtain: It is still not known whether there exists a number n such that χ(G×H) ≥ 4 for all directed graphs G, H with χ(G) ≥ χ(H) ≥ n. In fact, we prove that for every integer n ≥ 4, there exist directed graphs Gn, Hn such that χ(Gn) = n, χ(Hn) = 4 and χ(Gn×Hn) = 3.  相似文献   

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

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

京公网安备 11010802026262号