共查询到20条相似文献,搜索用时 515 毫秒
1.
2.
3.
《Discrete Mathematics》2022,345(8):112917
Let and denote the flow number and the circular flow number of a flow-admissible signed graph , respectively. It is known that for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that holds also for every flow-admissible signed graph . This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory. For cubic graphs we show that if and only if and if , then . We also prove that all pairs of flow number and circular flow number that fulfil these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless signed cubic graphs. Finally, we prove that all currently known flow-admissible graphs without nowhere-zero 5-flow have flow number and circular flow number 6 and propose several conjectures in this area. 相似文献
4.
5.
6.
7.
8.
《Discrete Mathematics》2022,345(8):112904
Let be the minimum integer such that every plane graph with girth g at least , minimum degree and no -paths consisting of vertices of degree 2, where , has a 3-vertex with at least t neighbors of degree 2, where .In 2015, Jendrol' and Maceková proved . Later on, Hudák et al. established , Jendrol', Maceková, Montassier, and Soták proved , and , and we recently proved that and .Thus is already known for and all t. In this paper, we prove that , , and whenever . 相似文献
9.
《Discrete Mathematics》2022,345(1):112669
In this paper, we consider two kinds of spectral extremal questions. The first asks which graph attains the maximum Q-index over all graphs of order n and size ? The second asks which graph attains the maximum Q-index over all -bipartite graphs with edges? We solve the first question for , and the second question for . The maximum Q-index on connected -bipartite graphs is also determined for . 相似文献
11.
《Discrete Mathematics》2022,345(1):112631
For a graph , a total ordering L on V, and a vertex , let be the set of vertices for which there is a path from v to w whose length is 0, 1 or 2 and whose L-least vertex is w. The weak 2-coloring number of G is the least k such that there is a total ordering L on V with for all vertices . We improve the known upper bound on the weak 2-coloring number of planar graphs from 28 to 23. As the weak 2-coloring number is the best known upper bound on the star list chromatic number of planar graphs, this bound is also improved. 相似文献
12.
13.
《Discrete Mathematics》2022,345(2):112675
We consider the binomial random graph , where p is a constant, and answer the following two questions.First, given , what is the maximum k such that a.a.s. the binomial random graph has an induced subgraph with k vertices and edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small ). Moreover, for every constant , with probability bounded away from 0, the size of the concentration set is bigger than , and, for every , a.a.s. it is smaller than .Second, given , what is the maximum μ such that a.a.s. the set of sizes of k-vertex subgraphs of contains a full interval of length μ? The answer is . 相似文献
14.
15.
16.
17.
18.
19.
《Discrete Mathematics》2022,345(10):112984
Let G be a generalized dicyclic group with identity 1. An inverse closed subset S of is called minimal if and there exists some such that . In this paper, we characterize distance-regular Cayley graphs of G under the condition that S is minimal. 相似文献
20.
We construct a minimal free resolution of the semigroup ring in terms of minimal resolutions of and when is a numerical semigroup obtained by gluing two numerical semigroups and . Using our explicit construction, we compute the Betti numbers, graded Betti numbers, regularity and Hilbert series of , and prove that the minimal free resolution of has a differential graded algebra structure provided the resolutions of and possess them. We discuss the consequences of our results in small embedding dimensions. Finally, we give an extension of our main result to semigroups in . 相似文献