共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Let G=(V,E) be a connected graph of order n, t a real number with t?1 and M⊆V(G) with . In this paper, we study the problem of some long paths to maintain their one or two different endpoints in M. We obtain the following two results: (1) for any vertex v∈V(G), there exists a vertex u∈M and a path P with the two endpoints v and u to satisfy , , dG(u)+1-t}; (2) there exists either a cycle C to cover all vertices of M or a path P with two different endpoints u0 and up in M to satisfy , where . 相似文献
3.
Let D=(V(D),A(D)) be a digraph. The competition graph of D, is the graph with vertex set V(D) and edge set . The double competition graph of D, is the graph with vertex set V(D) and edge set . A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R2 and there is an arc going from a vertex (x1,y1) to a vertex (x2,y2) if and only if x1>x2 and y1>y2. We show that a graph is the competition graph of a poset of dimension at most two if and only if it is an interval graph, at least half of whose maximal cliques are isolated vertices. This answers an open question on the doubly partial order competition number posed by Cho and Kim. We prove that the double competition graph of a poset of dimension at most two must be a trapezoid graph, generalizing a result of Kim, Kim, and Rho. Some connections are also established between the minimum numbers of isolated vertices required to be added to change a given graph into the competition graph, the double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph. 相似文献
4.
Iiro Honkala 《Discrete Mathematics》2006,306(21):2670-2681
Assume that G=(V,E) is an undirected graph, and C⊆V. For every v∈V, we denote by I(v) the set of all elements of C that are within distance one from v. If all the sets I(v) for v∈V?C are non-empty, and pairwise different, then C is called a locating-dominating set. The smallest possible density of a locating-dominating set in the infinite triangular grid is shown to be . 相似文献
5.
Oscar Rojo 《Linear algebra and its applications》2008,428(4):754-764
Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let Cr be the unique cycle of G. The graph G-E(Cr) is a forest of r rooted trees T1,T2,…,Tr with root vertices v1,v2,…,vr, respectively. Let
6.
Mark M. Malamud 《Journal of Functional Analysis》2011,260(3):613-638
The classical Weyl-von Neumann theorem states that for any self-adjoint operator A0 in a separable Hilbert space H there exists a (non-unique) Hilbert-Schmidt operator C=C? such that the perturbed operator A0+C has purely point spectrum. We are interesting whether this result remains valid for non-additive perturbations by considering the set ExtA of self-adjoint extensions of a given densely defined symmetric operator A in H and some fixed . We show that the ac-parts and of and A0 are unitarily equivalent provided that the resolvent difference is compact and the Weyl function M(⋅) of the pair {A,A0} admits weak boundary limits M(t):=w-limy→+0M(t+iy) for a.e. t∈R. This result generalizes the classical Kato-Rosenblum theorem. Moreover, it demonstrates that for such pairs {A,A0} the Weyl-von Neumann theorem is in general not true in the class ExtA. 相似文献
7.
Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex 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 smallest cardinality of a total restrained dominating set of G. We show that if T is a tree of order n, then . Moreover, we show that if T is a tree of order , then . We then constructively characterize the extremal trees T of order n achieving these lower bounds. 相似文献
8.
Johannes H. Hattingh 《Discrete Applied Mathematics》2009,157(13):2846-2858
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γr(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then . 相似文献
9.
Ognjen Milatovic 《Journal of Mathematical Analysis and Applications》2004,295(2):513-526
We consider a Schrödinger-type differential expression , where ∇ is a C∞-bounded Hermitian connection on a Hermitian vector bundle E of bounded geometry over a manifold of bounded geometry (M,g) with metric g and positive C∞-bounded measure dμ, and V∈Lloc1(EndE) is a linear self-adjoint bundle map. We define the maximal operator HV,max associated to HV as an operator in L2(E) given by HV,maxu=HVu for all , where ∇∗∇u in is understood in distributional sense. We give a sufficient condition for the self-adjointness of HV,max. The proof adopts Kato's technique to our setting, but it requires a more general version of Kato's inequality for Bochner Laplacian operator as well as a result on the positivity of u∈L2(M) satisfying the equation (ΔM+b)u=ν, where ΔM is the scalar Laplacian on M, b>0 is a constant and ν?0 is a positive distribution on M. For local estimates, we use a family of cut-off functions constructed with the help of regularized distance on manifolds of bounded geometry. 相似文献
10.
On signed cycle domination in graphs 总被引:2,自引:0,他引:2
Baogen Xu 《Discrete Mathematics》2009,309(4):1007-1387
Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures. 相似文献
11.
Irène Charon 《Discrete Applied Mathematics》2006,154(8):1246-1253
Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree. 相似文献
12.
13.
Rachel Quinlan 《Linear algebra and its applications》2011,434(6):1580-2271
Let V be a vector space of dimension n over any field F. Extreme values for the possible dimension of a linear subspace of EndF(V) with a particular property are considered in two specific cases. It is shown that if E1 is a subspace of EndF(V) and there exists an endomorphism g of V, not in E1, such that for every hyperplane H of V some element of E1 agrees with g on H, then E1 has dimension at least . This answers a question that was posed by Szechtman in 2003. It is also shown that a linear subspace of Mn(F) in which no element possesses a non-zero eigenvalue in F may have dimension at most . The connection between these two properties, which arises from duality considerations, is discussed. 相似文献
14.
15.
C. Balbuena 《Discrete Mathematics》2006,306(6):539-551
Let G=(V,E) be a finite graph, where |V|=n?2 and |E|=e?1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,…,n+e} with the property that for every v∈V, for some constant h. Such a labeling is strong if λ(V)={1,2,…,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if , then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs. 相似文献
16.
Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γtr(G) (γr(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n?2 such that both G and are not isomorphic to P3, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds. 相似文献
17.
Asaf Levin 《Operations Research Letters》2004,32(4):316-319
Given an undirected graph G=(V,E), an edge cost c(e)?0 for each edge e∈E, a vertex prize p(v)?0 for each vertex v∈V, and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to find a subtree T′=(V′,E′) that maximizes , subject to . We present a (4+ε)-approximation algorithm. 相似文献
18.
Li-Ping Huang 《Linear algebra and its applications》2010,433(1):221-232
Denote by G=(V,∼) a graph which V is the vertex set and ∼ is an adjacency relation on a subset of V×V. In this paper, the good distance graph is defined. Let (V,∼) and (V′,∼′) be two good distance graphs, and φ:V→V′ be a map. The following theorem is proved: φ is a graph isomorphism ⇔φ is a bounded distance preserving surjective map in both directions ⇔φ is a distance k preserving surjective map in both directions (where k<diam(G)/2 is a positive integer), etc. Let D be a division ring with an involution such that both |F∩ZD|?3 and D is not a field of characteristic 2 with D=F, where and ZD is the center of D. Let Hn(n?2) be the set of n×n Hermitian matrices over D. It is proved that (Hn,∼) is a good distance graph, where A∼B⇔rank(A-B)=1 for all A,B∈Hn. 相似文献
19.
Ajit A. Diwan Josh B. Frye Michael J. Plantholt Shailesh K. Tipnis 《Discrete Mathematics》2011,(21):2556
Let D be a directed graph with vertex set V, arc set A, and order n. The graph underlyingD is the graph obtained from D by replacing each arc (u,v)∈A by an undirected edge {u,v} and then replacing each double edge by a single edge. An anti-directed (hamiltonian) cycleH in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in Busch et al. (submitted for publication) [3] that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed Hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in Busch et al. (submitted for publication) [3] to prove that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed 2-factor. 相似文献
20.
J. Gómez 《Discrete Mathematics》2008,308(15):3361-3372
Let G=(V,E) be a finite non-empty graph, where V and E are the sets of vertices and edges of G, respectively, and |V|=n and |E|=e. A vertex-magic total labeling (VMTL) is a bijection λ from V∪E to the consecutive integers 1,2,…,n+e with the property that for every v∈V, , for some constant h. Such a labeling is super if λ(V)={1,2,…,n}. In this paper, two new methods to obtain super VMTLs of graphs are put forward. The first, from a graph G with some characteristics, provides a super VMTL to the graph kG graph composed by the disjoint unions of k copies of G, for a large number of values of k. The second, from a graph G0 which admits a super VMTL; for instance, the graph kG, provides many super VMTLs for the graphs obtained from G0 by means of the addition to it of various sets of edges. 相似文献