共查询到20条相似文献,搜索用时 673 毫秒
1.
2.
3.
《Discrete Mathematics》2022,345(10):112998
Let G be a graph and let f be a positive integer-valued function on . In this paper, we show that if for all , , then G has a spanning tree T containing an arbitrary given matching such that for each vertex v, , where denotes the number of components of and denotes the number of components of the induced subgraph with the vertex set S. This is an improvement of several results. Next, we prove that if for all , , then G admits a spanning closed walk passing through the edges of an arbitrary given matching meeting each vertex v at most times. This result solves a long-standing conjecture due to Jackson and Wormald (1990). 相似文献
4.
《Discrete Mathematics》2022,345(7):112866
Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then . If G is allowed to be disconnected, then the upper bound for was obtained by Donald [7], which was improved to independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, is reached and so this bound is tight. If triangles are forbidden in G, then can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that , which improves the above result with . 相似文献
5.
Let be a Noetherian local ring and M a finitely generated R-module. The invariants and of M were introduced in [3] and [17] in order to measure the non-Cohen–Macaulayness and the non-sequential-Cohen–Macaulayness of M, respectively. Let be the filtration of M such that is the largest submodule of M of dimension less than for all and . In this paper we prove that if , then there exists a constant c such that for all good parameter ideals of M with respect to this filtration. Here is the reducibility index of on M. This is an extension of the main results of [19], [20], [24]. 相似文献
6.
7.
Sanming Zhou 《Journal of Pure and Applied Algebra》2019,223(3):931-947
We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of , with connection sets and , respectively, where () is an mth primitive root of unity, A a nonzero ideal of , and ? Euler's totient function. We call them the mth cyclotomic graph and the second kind mth cyclotomic graph, and denote them by and , respectively. We give a necessary and sufficient condition for to be a perfect t-code in and a necessary condition for to be such a code in , where is an integer and D an ideal of containing A. In the case when , is known as an Eisenstein–Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for to be a perfect t-code in , where with β dividing α. In the literature such conditions are known to be sufficient when and under an additional condition. We give a classification of all first kind Frobenius circulants of valency 2p and prove that they are all pth cyclotomic graphs, where p is an odd prime. Such graphs belong to a large family of Cayley graphs that are efficient for routing and gossiping. 相似文献
8.
9.
10.
11.
12.
13.
《Discrete Mathematics》2022,345(12):113079
A set D of vertices of a graph is irredundant if each non-isolated vertex of has a neighbour in that is not adjacent to any other vertex in D. The upper irredundance number is the largest cardinality of an irredundant set of G; an -set is an irredundant set of cardinality .The IR-graph of G has the -sets as vertex set, and sets D and are adjacent if and only if can be obtained from D by exchanging a single vertex of D for an adjacent vertex in . An IR-tree is an IR-graph that is a tree. We characterize IR-trees of diameter 3 by showing that these graphs are precisely the double stars , i.e., trees obtained by joining the central vertices of two disjoint stars . 相似文献
14.
15.
《Journal of Pure and Applied Algebra》2022,226(9):107058
Let R be a commutative noetherian ring of dimension d and M be a commutative, cancellative, torsion-free monoid of rank r. Then S-. Further, we define a class of monoids such that if is seminormal, then S-, where . As an application, we prove that for the Segre extension over R, S-. 相似文献
16.
17.
18.
《Discrete Mathematics》2022,345(10):113001
The linked double star , where , is the graph consisting of the union of two stars and with a path on c vertices joining the centers. Its Ramsey number is the smallest integer r such that every 2-coloring of the edges of a admits a monochromatic . In this paper, we study the Ramsey numbers of linked double stars when c is odd. In particular, we establish bounds on the value of and determine the exact value of if , or if and . 相似文献
19.
20.