Results 41 to 50 of about 842 (102)
Discussiones Mathematicae Graph Theory, 2017 We characterize the class L32$L_3^2 $ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs.
Metelsky Yury +2 more
doaj +1 more source
A Note on Near-factor-critical Graphs [PDF]
, 2014 A near-factor of a finite simple graph $G$ is a matching that saturates all vertices except one. A graph $G$ is said to be near-factor-critical if the deletion of any vertex from $G$ results in a subgraph that has a near-factor. We prove that a connected
Huang, Kuo-Ching, Lih, Ko-Wei
core
Graceful Labeling of Spider Graphs With at Most Five Legs
Journal of Applied Mathematics, Volume 2025, Issue 1, 2025.A graceful labeling of a graph G with q edges is an injection f from the vertices of G to the set {0, 1, ⋯, q} such that, when each edge uv is assigned the label |f(u) − f(v)|, the resulting edge labels are distinct. A spider graph is a tree with exactly one vertex of degree greater than 2, and this vertex is called the branch vertex. A leg of a spider
A. Panpa +3 more
wiley +1 more source
Decomposition of the Product of Cycles Based on Degree Partition
Discussiones Mathematicae Graph Theory, 2019 The Cartesian product of n cycles is a 2n-regular, 2n-connected and bi- pancyclic graph. Let G be the Cartesian product of n even cycles and let 2n = n1+ n2+ ・ ・ ・ + nkwith k ≥ 2 and ni≥ 2 for each i. We prove that if k = 2, then G can be decomposed into
Borse Y. M., Shaikh S. R.
doaj +1 more source
A vizing-type theorem for matching forests [PDF]
, 2000 A well known Theorem of Vizing states that one can colour the edges of a graph by $\Delta +\alpha$ colours, such that edges of the same colour form a matching.
Keijsper, J.C.M.
core +2 more sources
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 Study on Variants of Status Unequal Coloring in Graphs and Its Properties
Journal of Mathematics, Volume 2024, Issue 1, 2024.Let G∧ be a simple connected graph with vertex set ϑG∧ and edge set ξG∧. The status of a vertex p∈ϑG∧ is defined as ∑q≠pd(p, q). A subset P of ϑG∧ is called a status unequal dominating set (stu‐dominating set) of G∧; for every q∈ϑ−P, there exists p in P such that p and q are adjacent and st(p) ≠ st(q).
Parvathy Gnana Sambandam +4 more
wiley +1 more source
On the Isometric Path Partition Problem
Discussiones Mathematicae Graph Theory, 2021 The isometric path cover (partition) problem of a graph consists of finding a minimum set of isometric paths which cover (partition) the vertex set of the graph.
Manuel Paul
doaj +1 more source
A tight lower bound for the hardness of clutters
, 2017 A {\it clutter} (or {\it antichain} or {\it Sperner family}) $L$ is a pair $(V,E)$, where $V$ is a finite set and $E$ is a family of subsets of $V$ none of which is a subset of another.
Mkrtchyan, Vahan, Sargsyan, Hovhannes
core +1 more source
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