Results 41 to 50 of about 10,864 (212)
3-Rainbow Index and Forbidden Subgraphs [PDF]
Graphs and Combinatorics, 2017 11 ...
Xueliang Li +3 more
openaire +3 more sources
AKCE International Journal of Graphs and Combinatorics, 2017 The extremal number or simply denotes the maximal number of edges in a graph on vertices with forbidden subgraphs and . The exact number of is only known for up to and . There are upper and lower bounds of for other values of .
Novi H. Bong
doaj +1 more source
Discrete Mathematics & Theoretical Computer Science, 2018 We define a weakly threshold sequence to be a degree sequence $d=(d_1,\dots,d_n)$ of a graph having the property that $\sum_{i \leq k} d_i \geq k(k-1)+\sum_{i > k} \min\{k,d_i\} - 1$ for all positive $k \leq \max\{i:d_i \geq i-1\}$.
Michael D. Barrus
doaj +1 more source
Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous [PDF]
, 2002 We consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem.
C. T. Hoang +19 more
core +2 more sources
Some Characterizations and NP-Complete Problems for Power Cordial Graphs
Journal of Mathematics, 2023 A power cordial labeling of a graph G=VG,EG is a bijection f:VG⟶1,2,…,VG such that an edge e=uv is assigned the label 1 if fu=fvn or fv=fun, for some n∈N∪0 and the label 0 otherwise, and satisfy the number of edges labeled with 0 and the number of edges ...
C. M. Barasara, Y. B. Thakkar
doaj +1 more source
Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs
, 2013 Bedrossian characterized all pairs of forbidden subgraphs for a 2-connected graph to be Hamiltonian. Instead of forbidding some induced subgraphs, we relax the conditions for graphs to be Hamiltonian by restricting Ore- and Fan-type degree conditions on ...
Bedrossian +13 more
core +1 more source
Degree Powers in Graphs with Forbidden Subgraphs [PDF]
The Electronic Journal of Combinatorics, 2004 For every real $p>0$ and simple graph $G,$ set $$ f\left( p,G\right) =\sum_{u\in V\left( G\right) }d^{p}\left( u\right) , $$ and let $\phi\left( r,p,n\right) $ be the maximum of $f\left( p,G\right) $ taken over all $K_{r+1}$-free graphs $G$ of order $n.$ We prove that, if $0 < p < r,$ then$$ \phi\left( r,p,n\right) =f\left( p,T_{r ...
Béla Bollobás, Vladimir Nikiforov
openaire +3 more sources
Deficiency and Forbidden Subgraphs of Connected, Locally-Connected Graphs
Discussiones Mathematicae Graph Theory, 2020 A graph G is locally-connected if the neighbourhood NG(v) induces a connected subgraph for each vertex v in G. For a graph G, the deficiency of G is the number of vertices unsaturated by a maximum matching, denoted by def(G). In fact, the deficiency of a
Li Xihe, Wang Ligong
doaj +1 more source
The Price of Connectivity for Vertex Cover
, 2013 The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, the corresponding number is called the connected vertex cover number, and is
Camby, Eglantine +3 more
core +3 more sources
Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems [PDF]
, 2012 The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π in I and an instance I′ resulting from a local perturbation of I that consists of insertions or removals of a
B. Escoffier +14 more
core +1 more source