Results 21 to 30 of about 312 (179)
The graph grabbing game on {0,1}-weighted graphs
Results in Applied Mathematics, 2019 The graph grabbing game is a two-player game on a weighted connected graph in which two players, Alice and Bob, alternatively remove non-cut vertices one by one to gain the weights on them.
Soogang Eoh, Jihoon Choi
doaj +1 more source
Hereditary Equality of Domination and Exponential Domination in Subcubic Graphs
Discussiones Mathematicae Graph Theory, 2021 Let γ(G) and γe(G) denote the domination number and exponential domination number of graph G, respectively. Henning et al., in [Hereditary equality of domination and exponential domination, Discuss. Math. Graph Theory 38 (2018) 275–285] gave a conjecture:
Chen Xue-Gang, Wang Yu-Feng, Wu Xiao-Fei
doaj +1 more source
Electronic Notes in Discrete Mathematics, 2017 In descending generality I survey: five partial orderings of graphs, the induced-subgraph ordering, and examples like perfect, threshold, and mock threshold graphs. The emphasis is on how the induced subgraph ordering differs from other popular orderings and leads to different basic questions.
openaire +4 more sources
Ramsey-type Theorems with Forbidden Subgraphs [PDF]
Combinatorica, 2001 P. Erdős and A. Hajnal conjectured that for every finite graph \(H\) every \(H\)-free graph on \(n\) vertices contains a complete or empty subgraph of size \(n^{\varepsilon(H)}\). It is shown that if the conjecture holds for \(H_1\), \(H_2\) then it holds for the graph which is \(H_1\) with one vertex blown up to a copy of \(H_2\).
Alon, Noga +2 more
openaire +2 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 +3 more sources
Electronic Journal of Graph Theory and Applications, 2018 We find the structure of graphs that have no C4, $\overline{C}_4$, C5, S3, chair and co-chair as induced subgraphs. Then we deduce the structure of the graphs having no induced C4, $\overline{C_4}$, S3, chair and co-chair and the structure of the graphs ...
Salman Ghazal
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
Forbidden subgraphs in connected graphs
Theoretical Computer Science, 2004 Given a set $ =\{H_1,H_2,...\}$ of connected non acyclic graphs, a $ $-free graph is one which does not contain any member of $% $ as copy. Define the excess of a graph as the difference between its number of edges and its number of vertices. Let ${\gr{W}}_{k, }$ be theexponential generating function (EGF for brief) of connected $ $-free graphs ...
Ravelomanana, Vlady, Loÿs, Thimonier
openaire +2 more sources
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 +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