共查询到20条相似文献,搜索用时 46 毫秒
1.
Van Bang Le 《Periodica Mathematica Hungarica》1993,27(2):105-124
For a finite or infinite graphG, theGallai graph (G) ofG is defined as the graph whose vertex set is the edge setE(G) ofG; two distinct edges ofG are adjacent in (G) if they are incident but do not span a triangle inG. For any positive integert, thetth iterated Gallai graph
t
(G) ofG is defined by (
t–1(G)), where 0(G):=G. A graph is said to beGallai-mortal if some of its iterated Gallai graphs finally equals the empty graph. In this paper we characterize Gallai-mortal graphs in several ways. 相似文献
2.
Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a total dominating set if D is dominating, and the induced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total dominating set of G. A set DV(G) is a total outer-connected dominating set if D is total dominating, and the induced subgraph G[V(G)−D] is a connected graph. The total outer-connected domination number of G is the minimum cardinality of a total outer-connected dominating set of G. We characterize trees with equal total domination and total outer-connected domination numbers. We give a lower bound for the total outer-connected domination number of trees and we characterize the extremal trees. 相似文献
3.
LetG be a graph with vertex setV (G) and edge setE (G), and letg andf be two integer-valued functions defined on V(G) such thatg(x)⩽(x) for every vertexx ofV(G). It was conjectured that ifG is an (mg +m - 1,mf -m+1)-graph andH a subgraph ofG withm edges, thenG has a (g,f)-factorization orthogonal toH. This conjecture is proved affirmatively.
Project supported by the National Natural Science Foundation of China. 相似文献
4.
The flag complex of a graph G = (V, E) is the simplicial complex X(G) on the vertex set V whose simplices are subsets of V which span complete subgraphs of G. We study relations between the first eigenvalues of successive higher Laplacians of X(G). One consequence is the following:Theorem: Let λ2(G) denote the second smallest eigenvalue of the Laplacian of G. If
\,\frac{k}{k+1}|V|$$" align="middle" border="0">
then
Applications include a lower bound on the homological connectivity of the independent sets complex I(G), in terms of a new graph domination parameter Γ(G) defined via certain vector representations of G. This in turns implies Hall type theorems for systems of disjoint representatives in hypergraphs.Received: January 2004 Revised: August 2004 Accepted: August 2004 相似文献
5.
A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ
t
(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number
is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that for every simple
connected graph G of order n ≥ 3,
where d
2(v) is the number of vertices of G at distance 2 from v.
R. Khoeilar: Research supported by the Research Office of Azarbaijan University of Tarbiat Moallem. 相似文献
6.
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph
Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of
graphs. 相似文献
7.
LetX
G,H denote the Cayley graph of a finite groupG with respect to a subsetH. It is well-known that its automorphism groupA(XG,H) must contain the regular subgroupL
G corresponding to the set of left multiplications by elements ofG. This paper is concerned with minimizing the index [A(XG,H)LG] for givenG, in particular when this index is always greater than 1. IfG is abelian but not one of seven exceptional groups, then a Cayley graph ofG exists for which this index is at most 2. Nearly complete results for the generalized dicyclic groups are also obtained. 相似文献
8.
Given a finite setX and a family of feasible subsetsF ofX, the 0–1 polytope P (F is defined as the convex hull of all the characteristic vectors of members ofF We show that under a certain assumption a special type of face ofP(F) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, we propose a new heuristic for such problems and give results of our preliminary computational experiments for the maximum stable set problem.Supported by a JSPS Fellowship for Young Scientists.Supported by Grant-in-Aids for Co-operative Research (06740147) of the Ministry of Education, Science and Culture. 相似文献
9.
Lutz Volkmann 《Czechoslovak Mathematical Journal》2010,60(1):77-83
Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ
k
(G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that
$
\gamma _{k + 1} (G) \leqslant \frac{{|V(G)| + \gamma _k (G)}}
{2}.
$
\gamma _{k + 1} (G) \leqslant \frac{{|V(G)| + \gamma _k (G)}}
{2}.
相似文献
10.
Jafar Fathali Hossein T. Kakhki Rainer E. Burkard 《Central European Journal of Operations Research》2006,14(3):229-246
Let a graph G = (V, E) with vertex set V and edge set E be given. The classical graph version of the p-median problem asks for a subset
of cardinality p, so that the (weighted) sum of the minimum distances from X to all other vertices in V is minimized. We consider the semi-obnoxious case, where every vertex has either a positive or a negative weight. This gives rise to two different objective functions, namely the weighted sum of the minimum distances from X to the vertices in V\X and, differently, the sum over the minimum weighted distances from X to V\X. In this paper an Ant Colony algorithm with a tabu restriction is designed for both problems. Computational results show its superiority with respect to a previously investigated variable neighborhood search and a tabu search heuristic.This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung. 相似文献
11.
Dr. Michael Mrva 《Monatshefte für Mathematik》1975,80(2):131-140
The graphs considered are finite and undirected, loops do not occur. An induced subgraphI of a graphX is called animitation ofX, if
12.
Let G=(V(G),E(G)) be a finite connected undirected graph and WV(G) a subset of vertices. We are searching for a subset XV(G) such that WX and the subgraph induced on X is a tree. -completeness results and polynomial time algorithms are given assuming that the cardinality of W is fixed or not. Besides we give complexity results when X has to induce a path or when G is a weighted graph. We also consider problems where the cardinality of X has to be minimized. 相似文献
13.
N. V. Zhivkov 《Set-Valued Analysis》1995,3(2):195-209
For every uniformly convex Banach spaceX with dimX2 there is a residual setU in the Hausdorff metric spaceB(X) of bounded and closed sets inX such that the metric projection generated by a set fromU is two-valued and upper semicontinuous on a dense and everywhere continual subset ofX. For any two closed and separated subsetsM
1 andM
2 ofX the points on the equidistant hypersurface which have best approximations both inM
1 andM
2 form a dense G set in the induced topology.The author is partially supported by the National Fund for Scientific Research at the Bulgarian Ministry of Science and Education under contract MM 408/94. 相似文献
14.
The purpose of this note is to study the problem of cyclability under the condition called regional Ores condition. As a consequence, we get the hamiltonicity of a graph G for which Ores condition holds in each of k vertex subsets partitioning V(G) separately (regionally), provided that the graph is k connected.The work was done while two last authors were visiting L R I. This stay was partially supported by french-polish programme POLONIUM 相似文献
15.
A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ
tr
(G), is the minimum cardinality of a TRDS of G. Let G be a cubic graph of order n. In this paper we establish an upper bound on γ
tr
(G). If adding the restriction that G is claw-free, then we show that γ
tr
(G) = γ
t
(G) where γ
t
(G) is the total domination number of G, and thus some results on total domination in claw-free cubic graphs are valid for total restrained domination.
Research was partially supported by the NNSF of China (Nos. 60773078, 10832006), the ShuGuang Plan of Shanghai Education Development
Foundation (No. 06SG42) and Shanghai Leading Academic Discipline Project (No. S30104). 相似文献
16.
For a setS of points in the plane, letd
1>d
2>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd
k
. It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk
2. IfS consists of the vertices of a convex polygon and |S|constk
2, then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon. 相似文献
17.
Guiying Yan 《应用数学学报(英文版)》1997,13(4):371-375
LetG be a simple graph. Letg(x) andf(x) be integer-valued functions defined onV(G) withf(x)g(x)1 for allxV(G). It is proved that ifG is an (mg+m–1,mf–m+1)-graph andH is a [1,2]-subgraph withm edges, then there exists a (g,f)-factorization ofG orthogonal toH.This work is supported by China Postdoctoral Science Foundation and Shandong Youth Science Foundation. 相似文献
18.
In 1956, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows. 相似文献
19.
Lutz Volkmann 《Mathematica Slovaca》2011,61(6):851-858
Let k be a positive integer, and let G be a simple graph with vertex set V (G). A vertex of a graph G dominates itself and all vertices adjacent to it. A subset S ⊆ V (G) is a k-tuple dominating set of G if each vertex of V (G) is dominated by at least k vertices in S. The k-tuple domatic number of G is the largest number of sets in a partition of V (G) into k-tuple dominating sets. 相似文献
20.
WANGWEIFAN ZHANGKEMIN 《高校应用数学学报(英文版)》1997,12(4):455-462
A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g. 相似文献
|