共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
4.
The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which
- (1)
- the edges connecting vertices at consecutive levels have the same weight,
- (2)
- each set of children, in one or more levels, defines a weighted clique, and
- (3)
- cliques at the same level are isomorphic.
5.
6.
Irena Rusu 《Discrete Applied Mathematics》2008,156(5):662-672
Practical questions arising from (for instance) biological applications can often be expressed as classical optimization problems with specific, new features. We are interested here in the version of the maximum weight matching problem (on a graph G) obtained by (1) defining a set F of pairs of incompatible edges of G and (2) asking that the matching contains at most one edge in each given pair. Such a matching is called an odd matching. The graph T(F)=(VF,F), where VF is the set of edges of G occurring in at least one pair of F, is called the trace-graph of G and F.We motivate the introduction of the maximum weight odd-matching (abbreviated as Odd-MWM) problem and study its complexity with respect to two parameters: the type of graph G and the graph class T to which T(F) belongs.Our contribution includes:
- •
- A proof that Odd-MWM is NP-complete for 3-degree bipartite graphs when T(F) is a matching (i.e. when T is the class of 1-regular graphs), even if the weight function is constant.
- •
- A proof that Odd-MWM is NP-complete (for 3-degree bipartite graphs as well as for any larger class) if and only if T is a class of graphs with unbounded induced matching. Otherwise, Odd-MWM is polynomial.
- •
- A (Δ(T(F))+1)-approximate algorithm for Odd-MWM on general graphs. This algorithm becomes a χ(T(F))-approximate algorithm when the graph class T admits a polynomial algorithm for minimum vertex coloring.
7.
8.
9.
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, .
10.
For a set \({\mathcal{S}}\) of positive integers, a spanning subgraph F of a graph G is called an \({\mathcal{S}}\) -factor of G if \({\deg_F(x) \in \mathcal{S}}\) for all vertices x of G, where deg F (x) denotes the degree of x in F. We prove the following theorem on {a, b}-factors of regular graphs. Let r ≥ 5 be an odd integer and k be either an even integer such that 2 ≤ k < r/2 or an odd integer such that r/3 ≤ k < r/2. Then every r-regular graph G has a {k, r–k}-factor. Moreover, for every edge e of G, G has a {k, r–k}-factor containing e and another {k, r–k}-factor avoiding e. 相似文献
11.
S is a local maximum stable set of a graph G, and we write S∈Ψ(G), if the set S is a maximum stable set of the subgraph induced by S∪N(S), where N(S) is the neighborhood of S. In Levit and Mandrescu (2002) [5] we have proved that Ψ(G) is a greedoid for every forest G. The cases of bipartite graphs and triangle-free graphs were analyzed in Levit and Mandrescu (2003) [6] and Levit and Mandrescu (2007) [7] respectively.In this paper we give necessary and sufficient conditions for Ψ(G) to form a greedoid, where G is:
- (a)
- the disjoint union of a family of graphs;
- (b)
- the Zykov sum of a family of graphs;
- (c)
- the corona X°{H1,H2,…,Hn} obtained by joining each vertex x of a graph X to all the vertices of a graph Hx.
12.
Gábor N. Sárközy 《Discrete Mathematics》2008,308(10):1962-1972
In this paper we study the minimum degree condition for a Hamiltonian graph to have a 2-factor with k components. By proving a conjecture of Faudree et al. [A note on 2-factors with two components, Discrete Math. 300 (2005) 218-224] we show the following. There exists a real number ε>0 such that for every integer k?2 there exists an integer n0=n0(k) such that every Hamiltonian graph G of order n?n0 with has a 2-factor with k components. 相似文献
13.
Domingos M. Cardoso 《Linear algebra and its applications》2007,423(1):90-98
Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k1, τ1)-regular set S1 and a (k2, τ2)-regular set S2 such that k1 − τ1 = k2 − τ2 = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, , induced by π, and the adjacency matrix of the quotient graph is obtained from the adjacency matrix of G/π. 相似文献
14.
Maria Chudnovsky Alexandra FradkinPaul Seymour 《Journal of Combinatorial Theory, Series B》2012,102(1):93-101
A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v1,…,vn} in such a way that for each j, there are at most k edges uv such that u∈{v1,…,vj−1} and v∈{vj,…,vn}.We prove that for every set S of tournaments, the following are equivalent:
- •
- there is a digraph H such that H cannot be strongly immersed in any member of S,
- •
- there exists k such that every member of S has cutwidth at most k,
- •
- there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles.
15.
Let G be a Hausdorff topological group. It is shown that there is a class C of subspaces of G, containing all (but not only) precompact subsets of G, for which the following result holds:Suppose that for every real-valued discontinuous function on G there is a set A∈C such that the restriction mapping f|A has no continuous extension to G; then the following are equivalent:
- (i)
- the left and right uniform structures of G are equivalent,
- (ii)
- every left uniformly continuous bounded real-valued function on G is right uniformly continuous,
- (iii)
- for every countable set A⊂G and every neighborhood V of the unit e of G, there is a neighborhood U of e in G such that AU⊂VA.
16.
17.
Oscar Rojo 《Linear algebra and its applications》2009,430(1):532-882
A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:
- the generalized Bethe tree B,
- a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,
- a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,
- a graph obtained from the cycle Cr by attaching B, by its root, to each vertex of the cycle, and
- a tree obtained from the path Pr by attaching B, by its root, to each vertex of the path,
- is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.
18.
In the invited chapter Discrete Spatial Models of the book Handbook of Spatial Logics, we have introduced the concept of dimension for graphs, which is inspired by Evako’s idea of dimension of graphs [A.V. Evako, R. Kopperman, Y.V. Mukhin, Dimensional properties of graphs and digital spaces, J. Math. Imaging Vision 6 (1996) 109-119]. Our definition is analogous to that of (small inductive) dimension in topology. Besides the expected properties of isomorphism-invariance and monotonicity with respect to subgraph inclusion, it has the following distinctive features:
- •
- Local aspect. That is, dimension at a vertex is basic, and the dimension of a graph is obtained as the sup over its vertices.
- •
- Dimension of a strong product G×H is dim(G)+dim(H) (for non-empty graphs G,H).
19.
Xuding Zhu 《Discrete Mathematics》2009,309(18):5562-5568
Given a graph G and a positive integer p, χp(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χp(G) in terms of the k-colouring number of G for k=2p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χk+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:
- (a)
- For every positive integer p, χp(G) is bounded by a constant for all G∈K.
- (b)
- For every positive integer k, is bounded by a constant for all G∈K.
- (c)
- For every positive integer q, ∇q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.
20.
Peter M. Gruber 《Advances in Mathematics》2004,186(2):456-497
Minimum sums of moments or, equivalently, distortion of optimum quantizers play an important role in several branches of mathematics. Fejes Tóth's inequality for sums of moments in the plane and Zador's asymptotic formula for minimum distortion in Euclidean d-space are the first precise pertinent results in dimension d?2. In this article these results are generalized in the form of asymptotic formulae for minimum sums of moments, resp. distortion of optimum quantizers on Riemannian d-manifolds and normed d-spaces. In addition, we provide geometric and analytic information on the structure of optimum configurations. Our results are then used to obtain information on
- (i)
- the minimum distortion of high-resolution vector quantization and optimum quantizers,
- (ii)
- the error of best approximation of probability measures by discrete measures and support sets of best approximating discrete measures,
- (iii)
- the minimum error of numerical integration formulae for classes of Hölder continuous functions and optimum sets of nodes,
- (iv)
- best volume approximation of convex bodies by circumscribed convex polytopes and the form of best approximating polytopes, and
- (v)
- the minimum isoperimetric quotient of convex polytopes in Minkowski spaces and the form of the minimizing polytopes.