共查询到20条相似文献,搜索用时 78 毫秒
1.
2.
3.
4.
A coloring (partition) of the collection of all -subsets of a set is -regular if the number of times each element of appears in each color class (all sets of the same color) is the same number . We are interested in finding the conditions under which a given -regular coloring of is extendible to an -regular coloring of for and . The case was solved by Cruse, and due to its connection to completing partial symmetric latin squares, many related problems are extensively studied in the literature, but very little is known for . The case was solved by Häggkvist and Hellgren, settling a conjecture of Brouwer and Baranyai. The cases and were solved by Rodger and Wantland, and Bahmanian and Newman, respectively. In this paper, we completely settle the cases and . 相似文献
5.
6.
7.
8.
9.
Hugo A. Akitaya Matthew D. Jones Matias Korman Oliver Korten Christopher Meierfrankenfeld Michael J. Munje Diane L. Souvaine Michael Thramann Csaba D. Tóth 《Journal of Graph Theory》2023,102(1):35-66
Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph and an integer , a -district map of is a partition of into nonempty subsets, called districts, each of which induces a connected subgraph of . A switch is an operation that modifies a -district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all -district maps of a graph under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is PSPACE-complete to decide whether there exists a sequence of 1-switches that takes a given -district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial lengths is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that take a given -district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors. 相似文献
10.
11.
12.
13.
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. 相似文献
14.
15.
16.
Antonios Charalambopoulos Vanessa Markaki Drosos Kourounis 《Mathematical Methods in the Applied Sciences》2020,43(8):5032-5072
In this work, a novel approach for the solution of the inverse conductivity problem from one and multiple boundary measurements has been developed on the basis of the implication of the framework of functions. The space of the functions of bounded variation is recommended here as the most appropriate functional space hosting the conductivity profile under reconstruction. For the numerical investigation of the inversion of the inclusion problem, we propose and implement a suitable minimization scheme of an enriched—constructed herein—functional, by exploiting the inner structure of space. Finally, we validate and illustrate our theoretical results with numerical experiments. 相似文献
17.
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 . 相似文献
20.
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 . 相似文献