共查询到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.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2001,51(2):225-229
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
(G – v) < γ
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 e ∈ E(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.
Ilwoo Cho 《Complex Analysis and Operator Theory》2008,2(1):1-28
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.
Asaf Nachmias 《Geometric And Functional Analysis》2009,19(4):1171-1194
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
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:
10.
Claude Tardif 《Combinatorica》2005,25(5):625-632
We prove that the identity
|