Results 21 to 30 of about 127 (95)
Discussiones Mathematicae Graph Theory, 2022 The Turán number of a graph H, denoted by ex(n, H), is the maximum number of edges of an n-vertex simple graph having no H as a subgraph. Let Sℓ denote the star on ℓ + 1 vertices, and let k · Sℓ denote k disjoint copies of Sℓ. Erdős and Gallai determined
Li Sha-Sha, Yin Jian-Hua, Li Jia-Yun
doaj +1 more source
EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
Mathematika, Volume 66, Issue 2, Page 422-447, April 2020., 2020 Abstract We study the model Gα∪G(n,p) of randomly perturbed dense graphs, where Gα is any n‐vertex graph with minimum degree at least αn and G(n,p) is the binomial random graph. We introduce a general approach for studying the appearance of spanning subgraphs in this model using absorption.
Julia Böttcher +3 more
wiley +1 more source
Comparing Eccentricity-Based Graph Invariants
Discussiones Mathematicae Graph Theory, 2020 The first and second Zagreb eccentricity indices (EM1 and EM2), the eccentric distance sum (EDS), and the connective eccentricity index (CEI) are all recently conceived eccentricity-based graph invariants, some of which found applications in chemistry ...
Hua Hongbo, Wang Hongzhuan, Gutman Ivan
doaj +1 more source
A Note on Packing of Uniform Hypergraphs
Discussiones Mathematicae Graph Theory, 2022 We say that two n-vertex hypergraphs H1 and H2 pack if they can be found as edge-disjoint subhypergraphs of the complete hypergraph Kn. Whilst the problem of packing of graphs (i.e., 2-uniform hypergraphs) has been studied extensively since seventies ...
Konarski Jerzy +2 more
doaj +1 more source
Stability for the Erdős-Rothschild problem
Forum of Mathematics, Sigma, 2023 Given a sequence $\boldsymbol {k} := (k_1,\ldots ,k_s)$ of natural numbers and a graph G, let $F(G;\boldsymbol {k})$ denote the number of colourings of the edges of G with colours $1,\dots ,s$ , such that, for every $c \in \{1 ...
Oleg Pikhurko, Katherine Staden
doaj +1 more source
Extremal problems of double stars [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 In a generalized Tur\'an problem, two graphs $H$ and $F$ are given and the question is the maximum number of copies of $H$ in an $F$-free graph of order $n$. In this paper, we study the number of double stars $S_{k,l}$ in triangle-free graphs.
Ervin Győri +2 more
doaj +1 more source
The Hilton-Spencer Cycle Theorems Via Katona’s Shadow Intersection Theorem
Discussiones Mathematicae Graph Theory, 2023 A family 𝒜 of sets is said to be intersecting if every two sets in 𝒜 intersect. An intersecting family is said to be trivial if its sets have a common element.
Borg Peter, Feghali Carl
doaj +1 more source
Algorithms for minimum flows [PDF]
Computer Science Journal of Moldova, 2001 We present a generic preflow algorithm and several implementations of it, that solve the minimum flow problem in O(n2m) time.
Eleonor Ciurea, Laura Ciupal
doaj
A note on the k‐domination number of a graph
International Journal of Mathematics and Mathematical Sciences, Volume 13, Issue 1, Page 205-206, 1990., 1989 The k‐domination number of a graph G = G(V, E), γk(G), is the least cardinality of a set X ⊂ V such that any vertex in VX is adjacent to at least k vertices of X. Extending a result of Cockayne, Gamble and Shepherd [4], we prove that if , n ≥ 1, k ≥ 1 then, , where p is the order of G.
Y. Caro, Y. Roditty
wiley +1 more source
On the discrepancy of coloring finite sets
International Journal of Mathematics and Mathematical Sciences, Volume 13, Issue 4, Page 825-827, 1990., 1990 Given a subset S of {1, …, n} and a map X : {1, …, n} → {−1, 1}, (i.e. a coloring of {1, …, n} with two colors, say red and blue) define the discrepancy of S with respect to X to be dX(S)=|∑i∈SX(i)| (the difference between the reds and blues on S).
D. Hajela
wiley +1 more source