Results 41 to 50 of about 807 (75)
Independence Number, Connectivity and All Fractional (a, b, k)-Critical Graphs
Discussiones Mathematicae Graph Theory, 2019 Let G be a graph and a, b and k be nonnegative integers with 1 ≤ a ≤ b. A graph G is defined as all fractional (a, b, k)-critical if after deleting any k vertices of G, the remaining graph has all fractional [a, b]-factors.
Yuan Yuan, Hao Rong-Xia
doaj +1 more source
Covering the Edges of a Random Hypergraph by Cliques
Discussiones Mathematicae Graph Theory, 2022 We determine the order of magnitude of the minimum clique cover of the edges of a binomial, r-uniform, random hypergraph G(r)(n, p), p fixed. In doing so, we combine the ideas from the proofs of the graph case (r = 2) in Frieze and Reed [Covering the ...
Rödl Vojtěch, Ruciński Andrzej
doaj +1 more source
Alliance free and alliance cover sets
, 2008 A \emph{defensive} (\emph{offensive}) $k$-\emph{alliance} in $\Gamma=(V,E)$ is a set $S\subseteq V$ such that every $v$ in $S$ (in the boundary of $S$) has at least $k$ more neighbors in $S$ than it has in $V\setminus S$.
H. Fernau +13 more
core +1 more source
A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs [PDF]
, 2006 We show that the number of $k$-matching in a given undirected graph $G$ is equal to the number of perfect matching of the corresponding graph $G_k$ on an even number of vertices divided by a suitable factor.
Friedland, Shmuel, Levy, Daniel
core +1 more source
Gregarious Kite Factorization of Tensor Product of Complete Graphs
Discussiones Mathematicae Graph Theory, 2020 A kite factorization of a multipartite graph is said to be gregarious if every kite in the factorization has all its vertices in different partite sets. In this paper, we show that there exists a gregarious kite factorization of Km × Kn if and only if mn
Tamil Elakkiya A., Muthusamy A.
doaj +1 more source
The Cartesian product of graphs with loops [PDF]
, 2014 We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi-Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one ...
Christiaan E. Van De Woestijne +7 more
core
Strong Tutte Type Conditions and Factors of Graphs
Discussiones Mathematicae Graph Theory, 2020 Let odd(G) denote the number of odd components of a graph G and k ≥ 2 be an integer. We give sufficient conditions using odd(G − S) for a graph G to have an even factor.
Yan Zheng, Kano Mikio
doaj +1 more source
Arbitrarily Partitionable {2K2, C4}-Free Graphs
Discussiones Mathematicae Graph Theory, 2022 A graph G = (V, E) of order n is said to be arbitrarily partitionable if for each sequence λ = (λ1, λ2, …, λp) of positive integers with λ1 +·…·+λp = n, there exists a partition (V1, V2, …, Vp) of the vertex set V such that Vi induces a connected ...
Liu Fengxia +2 more
doaj +1 more source
Eigenvalues and Perfect Matchings [PDF]
AMS classification: 05C50, 05C70, 05E30.graph;perfect matching;Laplacian matrix;eigenvalues.
Brouwer, A.E., Haemers, W.H.
core +1 more source
Sharp Upper Bounds on the Clar Number of Fullerene Graphs
Discussiones Mathematicae Graph Theory, 2018 The Clar number of a fullerene graph with n vertices is bounded above by ⌊n/6⌋ − 2 and this bound has been improved to ⌊n/6⌋ − 3 when n is congruent to 2 modulo 6.
Gao Yang, Zhang Heping
doaj +1 more source