Problem on Graph Theory and Algorithms

Click For Summary
SUMMARY

The discussion centers on demonstrating that if vw ∈ E(G) and f(v) ≠ f(w), then the graph G has an induced P4 subgraph. The function f is defined as f(v) = min{u | u ∈ V, dG(v, u) ≤ 2}. Participants express confusion regarding the demonstration process, and a reference to a similar question on Stack Exchange is provided for further clarification.

PREREQUISITES
  • Understanding of graph theory concepts, specifically induced subgraphs.
  • Familiarity with the function notation and definitions in graph theory.
  • Knowledge of distance functions in graphs, particularly dG(v, u).
  • Basic comprehension of connected components in graph theory.
NEXT STEPS
  • Review the properties of induced subgraphs in graph theory.
  • Study the concept of distance in graphs, focusing on dG(v, u).
  • Explore the implications of P4-free graphs and their characteristics.
  • Investigate the relationship between connected components and vertex functions in graph theory.
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in algorithms and properties of graphs.

iany00
Messages
1
Reaction score
0
G = (V, E) a graph with V = {1, . . . , n}. We have the function f : V → V defined
f (v) = min{u|u ∈ V, dG (v, u) ≤ 2}.Demostrate that vw ∈ E(G) with f (v) != f (w) then G has the
P4 subgraph induced

I don;t understand what to demostrate/to do. Any advice?
 
Physics news on Phys.org
iany00 said:
G = (V, E) a graph with V = {1, . . . , n}. We have the function f : V → V defined
f (v) = min{u|u ∈ V, dG (v, u) ≤ 2}.Demostrate that vw ∈ E(G) with f (v) != f (w) then G has the
P4 subgraph induced

I don;t understand what to demostrate/to do. Any advice?

Hi iany00, :)

I don't know the answer to your question, but the exact same question (although differently worded), is asked at Stack Exchange.

graph theory - Prove that if $G$ is P4-free then any two vertices $u$ and $v$ are in the same connected component if and only if $f(u) = f(v)$ - Mathematics

Hope this helps.

Kind Regards,
Sudharaka.
 

Similar threads

MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
MHB Find total number of republications
  • · Replies 22 ·
Replies
22
Views
2K
MHB Is HSC NP-Complete in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Probability of Having a Totally Dominating Set (Probabilistic Methods)
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Graph Theory: Does a Graph Have Cardinality?
  • · Replies 2 ·
Replies
2
Views
2K
MHB Applying Dijkstra Algorithm: Solving a Problem
  • · Replies 6 ·
Replies
6
Views
2K
MHB Finding a Minimal Vertex Cover & Max Sets for a Graph
  • · Replies 2 ·
Replies
2
Views
2K
MHB Problem on Graph Theory and Algorithms
  • · Replies 2 ·
Replies
2
Views
3K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
  • · Replies 4 ·
Replies
4
Views
2K
MHB Prim's algorithm-Minimum Spanning Tree
  • · Replies 8 ·
Replies
8
Views
3K