Results 11 to 20 of about 332 (184)
Splits with forbidden subgraphs [PDF]
Discrete Mathematics, 2022 In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be "split" such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(
Maria Axenovich, Ryan R. Martin
openaire +3 more sources
Forbidden Subgraphs of Power Graphs [PDF]
The Electronic Journal of Combinatorics, 2021 The undirected power graph (or simply power graph) of a group $G$, denoted by $P(G)$, is a graph whose vertices are the elements of the group $G$, in which two vertices $u$ and $v$ are connected by an edge between if and only if either $u=v^i$ or $v=u^j$ for some $i$, $j$.
Pallabi Manna +2 more
openaire +6 more sources
Maximal independence and regularity of Al/Si distributions in disordered phyllosilicates 2:1. [PDF]
Acta Crystallogr A Found AdvThe distribution of aluminium cations in disordered phyllosilicates is analysed according to the concepts of maximal independence and regularity.As an extension of previous works, we analyse regularity in disordered Al/Si distributions in phyllosilicates 2:1. The method is based on an analysis of maximal independent sets in a labelled quotient graph of
Moreira de Oliveira M, Eon JG.
europepmc +2 more sources
Toughness, Forbidden Subgraphs and Pancyclicity [PDF]
Graphs and Combinatorics, 2021 AbstractMotivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such that every 1-tough H-free graph is hamiltonian. The almost complete answer was given there by the conclusion that every proper induced subgraph H of $$K_1\cup P_4$$
Wei Zheng 0008 +2 more
openaire +2 more sources
Forbidden subgraph decomposition
Discrete Mathematics, 2002 no ...
Rusu, Irena, Spinrad, Jeremy P.
openaire +2 more sources
On Minrank and Forbidden Subgraphs [PDF]
ACM Transactions on Computation Theory, 2019 The minrank over a field F of a graph G on the vertex set { 1,2,… , n } is the minimum possible rank of a matrix M ∈ F n × n such that M
openaire +5 more sources
Forbidden subgraphs for chorded pancyclicity
Discrete Mathematics, 2017 We call a graph $G$ pancyclic if it contains at least one cycle of every possible length $m$, for $3\le m\le |V(G)|$. In this paper, we define a new property called chorded pancyclicity. We explore forbidden subgraphs in claw-free graphs sufficient to imply that the graph contains at least one chorded cycle of every possible length $4, 5, \ldots, |V(G)|
Megan Cream +2 more
openaire +4 more sources
Complexity Framework For Forbidden Subgraphs.
CoRR, 2022 For any finite set H={H1,…,Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,…,Hp as a subgraph. Similar to known meta-classifications for the minor and topological minor relations, we give a meta-classification for the subgraph relation.
Matthew Johnson 0002 +6 more
openaire +2 more sources
On hamiltonicity of 1-tough triangle-free graphs
Electronic Journal of Graph Theory and Applications, 2021 Let ω(G) denote the number of components of a graph G. A connected graph G is said to be 1-tough if ω(G − X)≤|X| for all X ⊆ V(G) with ω(G − X)>1. It is well-known that every hamiltonian graph is 1-tough, but that the reverse statement is not true in ...
Wei Zheng, Hajo Broersma, Ligong Wang
doaj +1 more source
Upward-closed hereditary families in the dominance order [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 The majorization relation orders the degree sequences of simple graphs into posets called dominance orders. As shown by Ruch and Gutman (1979) and Merris (2002), the degree sequences of threshold and split graphs form upward-closed sets within the ...
Michael D. Barrus, Jean A. Guillaume
doaj +1 more source