Induced forests in cubic graphs (Q791532): Difference between revisions

Let G be a graph with vertex set V(G). Denote \(f(G)=\max \quad \{| A| /| V(G)|;A\subset V(G),\) A induces a fores\(t\}\). The author derives bounds on f(G) and consequently calculates that lim \(\inf_{n\to \infty}\{f(G)\); G is a cubic graph with girth at least \(n\}\) equals to 3/4.

0 references

zbMATH Keywords

cubic graph

0 references

girth

0 references

forest

0 references

independence ratio

0 references

reviewed by

Peter Horák

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

On the independence ratio of a graph

0 references

The Independence Ratio of Regular Graphs

0 references

The point-arboricity of a graph

0 references

Girth and Independence Ratio

0 references

Q4063170

0 references

Q4073393

0 references

Identifiers

zbMATH Open document ID

0536.05015

0 references

DOI

10.1016/0012-365X(84)90115-8

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:791532

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+On the independence ratio of a graph
@@ Property / cites work: On the independence ratio of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+The Independence Ratio of Regular Graphs
@@ Property / cites work: The Independence Ratio of Regular Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The point-arboricity of a graph
@@ Property / cites work: The point-arboricity of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Girth and Independence Ratio
@@ Property / cites work: Girth and Independence Ratio / rank @@
+Normal rank
@@ Property / cites work @@
+Q4063170
@@ Property / cites work: Q4063170 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4073393
@@ Property / cites work: Q4073393 / rank @@
+Normal rank