共查询到20条相似文献,搜索用时 397 毫秒
1.
A graph with at least vertices is said to be distance -extendable if, for any matching of with edges in which the edges lie at distance at least pairwise, there exists a perfect matching of containing . In this paper we prove that every 5-connected triangulation on the projective plane of even order is distance 3 7-extendable and distance 4 -extendable for any . 相似文献
2.
3.
A compact graph-like space is a triple , where is a compact, metrizable space, is a closed zero-dimensional subset, and is an index set such that . New characterizations of compact graph-like spaces are given, connecting them to certain classes of continua, and to standard subspaces of Freudenthal compactifications of locally finite graphs. These are applied to characterize Eulerian graph-like compacta. 相似文献
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
While much attention has been directed to the maximum modulus and maximum real part of chromatic roots of graphs of order (ie, with vertices), relatively little is known about the maximum imaginary part of such graphs. We prove that the maximum imaginary part can grow linearly in the order of the graph. We also show that for any fixed , almost every random graph in the Erdös-Rényi model has a nonreal root. 相似文献
14.
15.
16.
Ademir Hujdurović 《Journal of Graph Theory》2020,95(4):543-564
A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique in a vertex-transitive graph is strong if and only if for every maximal independent set of . On the basis of this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable. 相似文献
17.
Win conjectured that a graph on vertices contains disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least , where is even and . In this paper, we prove that Win's conjecture is true for , where is sufficiently large. To show this result, we prove a theorem on -factor in a graph under some Ore-type condition. Our main tools include Tutte's -factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization and the solution to the long-standing 1-factor decomposition conjecture. 相似文献
18.
19.
The distinguishing index of a graph is the least cardinal number such that has an edge-coloring with colors, which is preserved only by the trivial automorphism. We prove a general upper bound for any connected infinite graph with finite maximum degree . This is in contrast with finite graphs since for every there exist infinitely many connected, finite graphs with . We also give examples showing that this bound is sharp for any maximum degree . 相似文献