Results 31 to 40 of about 652,005 (320)
Split graphs and Nordhaus–Gaddum graphs
Discrete Mathematics, 2016 25 ...
Cheng, Christine +2 more
openaire +3 more sources
Token Sliding on Split Graphs [PDF]
Theory of Computing Systems, 2020 We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent.
Belmonte, Rémy +5 more
openaire +5 more sources
Split domination of splitted graphs
, 2021 In this paper, we introduce and investigate some new splitted graphs called \(S(P_l); S(H_l); S(P^+_l ), S(P_loNK_1) .\) Also we discuss some splitted graphs and it's properties are obtained.
, A.Esakkimuthu, Nethaji, O.
openaire +1 more source
The Bipartite-Splittance of a Bipartite Graph
Discussiones Mathematicae Graph Theory, 2019 A bipartite-split graph is a bipartite graph whose vertex set can be partitioned into a complete bipartite set and an independent set. The bipartite- splittance of an arbitrary bipartite graph is the minimum number of edges to be added or removed in ...
Yin Jian-Hua, Guan Jing-Xin
doaj +1 more source
On the Intersection Graphs Associeted to Posets
Discussiones Mathematicae - General Algebra and Applications, 2020 Let (P, ≤) be a poset with the least element 0. The intersection graph of ideals of P, denoted by G(P), is a graph whose vertices are all nontrivial ideals of P and two distinct vertices I and J are adjacent if and only if I ∩ J ≠ {0}.
Afkhami M. +2 more
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
Computing the split domination number of grid graphs
Indonesian Journal of Combinatorics, 2021 A set D - V is a dominating set of G if every vertex in V - D is adjacent to some vertex in D. The dominating number γ(G) of G is the minimum cardinality of a dominating set D.
V. R. Girish, P. Usha
doaj +1 more source
Pebbling in Semi-2-Trees [PDF]
, 2017 Graph pebbling is a network model for transporting discrete resources that are consumed in transit. Deciding whether a given configuration on a particular graph can reach a specified target is ${\sf NP}$-complete, even for diameter two graphs, and ...
Alcón, Liliana +2 more
core +3 more sources
Split-critical and uniquely split-colorable graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2010 Graphs and Algorithms The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as ...
Tınaz Ekim, Bernard Ries, D. de Werra
openalex +5 more sources
Procedia Computer Science, 2023 Given nonnegative integers, $s$ and $k$, an $(s,k)$-polar partition of a graph $G$ is a partition $(A,B)$ of $V_G$ such that $G[A]$ and $\overline{G[B]}$ are complete multipartite graphs with at most $s$ and $k$ parts, respectively. If $s$ or $k$ is replaced by $\infty$, it means that there is no restriction on the number of parts of $G[A]$ or ...
Mendoza, F. Esteban Contreras +1 more
openaire +2 more sources