Vertex Covers and Vertex Covering Numbers | Graph Theory
We introduce vertex covers, minimum vertex covers, and vertex covering numbers! We'll see some examples and non-examples of vertex covers, as well as minimum vertex covers and some that aren't minimum. The number of vertices in a minimum vertex cover is called the vertex covering number of the graph. We'll discuss why the complement of a vertex cover is an independent vertex set, and see how the covering number plus the independence number is the order of a graph (Gallai identity). We'll also discuss covering numbers of complete graphs, cycles, and complete bipartite graphs. #GraphTheory
A vertex is said to cover its incident edges. A set of vertices is a vertex cover is if covers every edge in the graph.
Independent Vertex Sets: • Independent Vertex Set...
Proof Complement of Vertex Cover is Independent Set: • Complement of Vertex C...
Proof Covering Number plus Independence Number is Order of Graph: (coming soon)
Graph Theory playlist: • Graph Theory
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: www.paypal.me/wrathofmath
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050
Пікірлер: 28
Check out the lesson on independent vertex sets if you need a recap! kzread.info/dash/bejne/Yqeow9ixdcbJpqg.html
Vertex covering numbers? More like "Very good lectures, that are better than others!" 👍
Thank you for your explanations - this was missing in my understanding of the NP Reduction between Independent Set and Vertex Cover
Great now I get it! Thanks a lot sir!
Thank you, thank you soo muchhh!! 🥺🙌🏻 That’s very helpful of you!
@WrathofMath
2 жыл бұрын
So glad it helped, thanks for watching!
Crystal clear explanation, thank you!!! I love how to explain the definitions of each specific terms, I always get confused by those cause it's hard for me to remember the details, you're literally the math teacher I needed growing up
@ceciliaw1065
Жыл бұрын
you*
@WrathofMath
Жыл бұрын
Thanks so much!
Thankyou sir, for easy and simple way of explanation.
@WrathofMath
Жыл бұрын
Glad to help!
thanks a lot
Hello and thank you for the helpful video! What is the name of graph theory textbook you mention here?
awesome video!
@WrathofMath
2 жыл бұрын
Thank you!
@aashsyed1277
2 жыл бұрын
@@WrathofMath you are welcome!
Thank you
@WrathofMath
Жыл бұрын
Glad to help!
Co- efficient of chromatic polynomial pls...
Thank you a lot for your videos. Do u have videos on edge covering? And random graphs? If not would like to have a videos on them. Kindly requesting you to do a videos on those topic. Thank you so much again. 🎉
@WrathofMath
Жыл бұрын
Thanks for watching! I have no videos on either topic. I can see about doing one on edge coverings, probably will be a while for a random graphs lesson though, haven't studied them much.
@MalithClicks
Жыл бұрын
@@WrathofMath okey okey, please try if you can. Thank you !
@WrathofMath
Жыл бұрын
kzread.info/dash/bejne/aXydt9Cdeq7MdbQ.html Currently unlisted but will be released tonight at midnight.
@MalithClicks
Жыл бұрын
@@WrathofMath wow!! 🎊🎊 😍 Thank you so much. 😍😍 Really appreciate what you are doing.
Proof Covering Number plus Independence Number is Order of Graph: (coming soon)??
Aww, the proof for a future video never came, it seems. Awesome video regardless!
@WrathofMath
11 ай бұрын
Which one do you mean? Here's one which I just added to the description (had forgot until now): kzread.info/dash/bejne/haBsl8yufKiucqg.html And I'll see if I can do the other soon, it has been too long since I made some good graph theory content! Thanks for watching!