Results 41 to 50 of about 10,088 (246)
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
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 +3 more sources
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 +4 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
Forbidden subgraphs on Hamiltonian index
Discrete Mathematics, 2020 Abstract Let G be a graph other than a path. The m -iterated line graph of a graph G is L m ( G ) = L ( L m − 1 ( G ) ) . where L 1 ( G ) denotes the line graph L ( G ) of G .
Xia Liu, Liming Xiong
openalex +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
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
On Critical Unicyclic Graphs with Cutwidth Four
AppliedMath, 2022 The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn with n=|V(G)| vertices in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized.
Zhenkun Zhang, Hongjian Lai
doaj +1 more source
Vertex Colouring and Forbidden Subgraphs ? A Survey [PDF]
Graphs and Combinatorics, 2004 The monograph ``Graph coloring problems'' by \textit{T. R. Jensen} and \textit{B. Toft} (Wiley, New York) (1995; Zbl 0855.05054) provides a comprehensive list of unsolved problems in chromatic graph theory. The present survey gives an account of the recent development in the area.
Randerath, Bert, Schiermeyer, Ingo
openaire +4 more sources
Theory and Applications of GraphsFor a family $\mathcal{H}$ of graphs, a graph $G$ is said to be $\mathcal{H}$-free if $G$ contains no member of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{G}_2^{(3)}}(\mathcal{H})$ denote the family of $2$-connected $\mathcal{H}$-free graphs ...
Takafumi Kotani, Yoshimi Egawa
doaj +1 more source