Results 31 to 40 of about 14,970 (213)
A characterization of extremal graphs with no matching-cut [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|≥\lceil 3(|V|-1)/2\rceil$ , and constructed a large class of immune graphs that attain this lower ...
Paul Bonsma
doaj +1 more source
Donaldson-Thomas invariants, torus knots, and lattice paths [PDF]
, 2018 In this paper we find and explore the correspondence between quivers, torus knots, and combinatorics of counting paths. Our first result pertains to quiver representation theory -- we find explicit formulae for classical generating functions and ...
Panfil, Miłosz +2 more
core +3 more sources
List graphs and distance-consistent node labelings
Electronic Journal of Graph Theory and Applications, 2018 In this paper we consider node labelings c of an undirected connected graph G = (V, E) with labels {1, 2, ..., ∣V∣}, which induce a list distance c(u, v) = ∣c(v) − c(u)∣ besides the usual graph distance d(u, v).
Håkan Lennerstad, Mattias Eriksson
doaj +1 more source
An extremal problem on trees and database theory [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We consider an extremal problem on labelled directed trees and applications to database theory. Among others, we will show explicit keysystems on an underlying set of size $n$, that cannot be represented by a database of less than $2^{n(1-c\cdot \log ...
Gyula O.H. Katona, Krisztián Tichler
doaj +1 more source
Shattered Sets and the Hilbert Function [PDF]
, 2016 We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions.
Moran, Shay, Rashtchian, Cyrus
core +1 more source
Hypergraphs with infinitely many extremal constructions
Discrete Analysis, 2023 Hypergraphs with infinitely many extremal constructions, Discrete Analysis 2023:18, 34 pp. A fundamental result in extremal graph theory, Turán's theorem, states that the maximal number of edges of a graph with $n$ vertices that does not contain a ...
Jianfeng Hou +4 more
doaj +1 more source
Pairwise Intersections and Forbidden Configurations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 Let $f_m(a,b,c,d)$ denote the maximum size of a family $\mathcal{F}$ of subsets of an $m$-element set for which there is no pair of subsets $A,B \in \mathcal{F}$ with $|A \cap B| \geq a$, $|\bar{A} \cap B| \geq b$, $|A \cap \bar{B}| \geq c$, and $|\bar{A}
Richard P. Anstee, Peter Keevash
doaj +1 more source
BPS counting for knots and combinatorics on words [PDF]
, 2016 We discuss relations between quantum BPS invariants defined in terms of a product decomposition of certain series, and difference equations (quantum A-polynomials) that annihilate such series.
Kucharski, Piotr, Sułkowski, Piotr
core +2 more sources
A question of Bukh on sums of dilates
Discrete Analysis, 2021 A question of Bukh on sums of dilates, Discrete Analysis 2021:13, 21 pp. Let $A$ and $B$ be subsets of an Abelian group. Their sumset $A+B$ is defined to be the set of all $a+b$ such that $a\in A$ and $b\in B$.
Brandon Hanson, Giorgis Petridis
doaj +1 more source
Vertex-Facet Incidences of Unbounded Polyhedra [PDF]
, 2000 How much of the combinatorial structure of a pointed polyhedron is contained in its vertex-facet incidences? Not too much, in general, as we demonstrate by examples. However, one can tell from the incidence data whether the polyhedron is bounded.
Joswig, Michael +3 more
core +4 more sources