共查询到20条相似文献,搜索用时 32 毫秒
1.
《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. 相似文献
2.
《Discrete Mathematics》2022,345(7):112893
In this paper, we study the Reconstruction Conjecture for finite simple graphs. Let Γ and be finite simple graphs with at least three vertices such that there exists a bijective map and for any , there exists an isomorphism . Then we define the associated directed graph with two kinds of arrows from the graphs Γ and , the bijective map f and the isomorphisms . By investigating the associated directed graph , we study when are the two graphs Γ and isomorphic. 相似文献
3.
4.
5.
6.
7.
A graph G is called a pseudo-core if every endomorphism of G is either an automorphism or a colouring. A graph G is a core if every endomorphism of G is an automorphism. Let be the finite field with q elements where q is a power of an odd prime number. The quadratic forms graph, denoted by where , has all quadratic forms on as vertices and two vertices f and g are adjacent whenever or 2. We prove that every is a pseudo-core. Further, when n is even, is a core. When n is odd, is not a core. On the other hand, we completely determine the independence number of . 相似文献
8.
《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 . 相似文献
9.
《Discrete Mathematics》2022,345(10):113004
Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G, can be partitioned into A and B such that is perfect and . We use and to denote a path and a cycle on t vertices, respectively. For two disjoint graphs and , we use to denote the graph with vertex set and edge set , and use to denote the graph with vertex set and edge set . In this paper, we prove that (i) -free graphs are perfectly divisible, (ii) if G is -free with , (iii) if G is -free, and (iv) if G is -free. 相似文献
10.
《Discrete Mathematics》2022,345(3):112717
A transversal set of a graph G is a set of vertices incident to all edges of G. The transversal number of G, denoted by , is the minimum cardinality of a transversal set of G. A simple graph G with no isolated vertex is called τ-critical if for every edge . For any τ-critical graph G with , it has been shown that by Erd?s and Gallai and that by Erd?s, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to . In this paper, we prove stronger results via spectrum. Let G be a τ-critical graph with and , and let denote the largest eigenvalue of the adjacency matrix of G. We show that with equality if and only if G is , , or , where ; and in particular, with equality if and only if G is . We then apply it to show that for any nonnegative integer r, we have and characterize all extremal graphs. This implies a pure combinatorial result that , which is stronger than Erd?s-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations. 相似文献
11.
《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). 相似文献
12.
13.
14.
15.
16.
Moshe Marcus 《Annales de l'Institut Henri Poincaré (C) Analyse Non Linéaire》2019,36(5):1183-1200
Consider operators of the form in a bounded Lipschitz domain . Assume that satisfies for every and γ is a number in a range described in the introduction. The model case is where F is a closed subset of ?Ω and Hardy constant for V. We provide sharp two sided estimates of the Green and Martin kernel for in Ω. In addition we establish a pointwise version of the 3G inequality. 相似文献
17.
18.
19.
20.