Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
27,090
result(s) for
"mathematics - combinatorics"
Sort by:
Secret history : the story of cryptology
\"Codes are a part of everyday life, from the ubiquitous Universal Price Code (UPC) to postal zip codes. They need not be intended for secrecy. They generally use groups of letters (sometimes pronounceable code words) or numbers to represent other words or phrases. There is typically no mathematical rule to pair an item with its representation in code. A few more examples will serve to illustrate the range of codes\"-- Provided by publisher.
Book
On the modkchromatic index of graphs
For a graphGand an integerk≥ 2 , aχ'_(k) -coloring ofGis an edge coloring ofGsuch that the subgraph induced by the edges of each color has all degrees congruent to1 (\\mod k) , andχ'_(k)(G)is the minimum number of colors in aχ'_(k) -coloring ofG . In [\"The modkchromatic index of graphs isO(k) \", J. Graph Theory. 2023; 102: 197-200], Botler, Colucci and Kohayakawa proved thatχ'_(k)(G)≤ 198k-101for every graphG . In this paper, we show thatχ'_(k)(G) ≤ 177k-93 .
Journal Article
The bipartite Ramsey numbersBR(C₈, C_(2n))
For the given bipartite graphsG₁,G₂,…,G_(t) , the multicolor bipartite Ramsey numberBR(G₁,G₂,…,G_(t))is the smallest positive integerbsuch that anyt -edge-coloring ofK_(b,b)contains a monochromatic subgraph isomorphic toGᵢ , colored with thei th color for some1≤ i≤ t . We compute the exact values of the bipartite Ramsey numbersBR(C₈,C_(2n))forn≥2 .
Journal Article
Proving exact values for the2 -limited broadcast domination number on grid graphs
We establish exact values for the2 -limited broadcast domination number of various grid graphs, in particularC_(m)□ C_(n)for3 ≤ m ≤ 6and alln≥ m ,P_(m) □ C₃for allm ≥ 3 , andP_(m) □ C_(n)for4≤ m ≤ 5and alln ≥ m . We also produce periodically optimal values forP_(m) □ C₄andP_(m) □ C₆form ≥ 3 ,P₄ □ P_(n)forn ≥ 4 , andP₅ □ P_(n)forn ≥ 5 . Our method completes an exhaustive case analysis and eliminates cases by combining tools from linear programming with various mathematical proof techniques.
Journal Article
On the genera of polyhedral embeddings of cubic graph
In this article we present theoretical and computational results on the existence of polyhedral embeddings of graphs. The emphasis is on cubic graphs. We also describe an efficient algorithm to compute all polyhedral embeddings of a given cubic graph and constructions for cubic graphs with some special properties of their polyhedral embeddings. Some key results are that even cubic graphs with a polyhedral embedding on the torus can also have polyhedral embeddings in arbitrarily high genus, in fact in a genus close to the theoretical maximum for that number of vertices, and that there is no bound on the number of genera in which a cubic graph can have a polyhedral embedding. While these results suggest a large variety of polyhedral embeddings, computations for up to 28 vertices suggest that by far most of the cubic graphs do not have a polyhedral embedding in any genus and that the ratio of these graphs is increasing with the number of vertices.
Journal Article
Algorithmics of matching under preferences
Matching problems with preferences are all around us: they arise when agents seek to be allocated to one another on the basis of ranked preferences over potential outcomes. Efficient algorithms are needed for producing matchings that optimise the satisfaction of the agents according to their preference lists. In recent years there has been a sharp increase in the study of algorithmic aspects of matching problems with preferences, partly reflecting the growing number of applications of these problems worldwide. The importance of the research area was recognised in 2012 through the award of the Nobel Prize in Economic Sciences to Alvin Roth and Lloyd Shapley.
eBook
The complexity of recognizingABAB -free hypergraphs
The study of geometric hypergraphs gave rise to the notion ofABAB -free hypergraphs. A hypergraph𝓗is calledABAB -free if there is an ordering of its vertices such that there are no hyperedgesA,Band verticesv₁,v₂,v₃,v₄in this order satisfyingv₁,v₃∈ A∖ Bandv₂,v₄∈ B∖ A . In this paper, we prove that it is NP-complete to decide if a hypergraph isABAB -free. We show a number of analogous results for hypergraphs with similar forbidden patterns, such asABABA -free hypergraphs. As an application, we show that deciding whether a hypergraph is realizable as the incidence hypergraph of points and pseudodisks is also NP-complete.
Journal Article
Euleriank -dominating reconfiguration graphs
For a graphG , the vertices of thek -dominating graph, denoted𝓓_(k)(G) , correspond to the dominating sets ofGwith cardinality at mostk . Two vertices of𝓓_(k)(G)are adjacent if and only if the corresponding dominating sets inGcan be obtained from one other by adding or removing a single vertex ofG . Since𝓓_(k)(G)is not necessarily connected whenk < |V(G)| , much research has focused on conditions under which𝓓_(k)(G)is connected and recent work has explored the existence of Hamilton paths in thek -dominating graph. We consider the complementary problem of determining the conditions under which thek -dominating graph is Eulerian. In the case wherek = |V(G)| , we characterize those graphsGfor which𝓓_(k)(G)is Eulerian. In the case wherekis restricted, we determine for a number of graph classes, the conditions under which thek -dominating graph is Eulerian.
Journal Article
Exponential multivalued forbidden configurations
The forbidden number$\\mathrm{forb}(m,F)$ , which denotes the maximum number of unique columns in an$m$ -rowed$(0,1)$ -matrix with no submatrix that is a row and column permutation of$F$ , has been widely studied in extremal set theory. Recently, this function was extended to$r$ -matrices, whose entries lie in$\\{0,1,\\dots,r-1\\}$ . The combinatorics of the generalized forbidden number is less well-studied. In this paper, we provide exact bounds for many$(0,1)$ -matrices$F$ , including all$2$ -rowed matrices when$r > 3$ . We also prove a stability result for the$2\\times 2$identity matrix. Along the way, we expose some interesting qualitative differences between the cases$r=2$ ,$r = 3$ , and$r > 3$ .
Journal Article
Wiener Index and Remoteness in Triangulations and Quadrangulations
Let$G$be a a connected graph. The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide asymptotic formulae for the maximum Wiener index of simple triangulations and quadrangulations with given connectivity, as the order increases, and make conjectures for the extremal triangulations and quadrangulations based on computational evidence. If$\\overline{\\sigma}(v)$denotes the arithmetic mean of the distances from$v$to all other vertices of$G$ , then the remoteness of$G$is defined as the largest value of$\\overline{\\sigma}(v)$over all vertices$v$of$G$ . We give sharp upper bounds on the remoteness of simple triangulations and quadrangulations of given order and connectivity.
Journal Article