Network Connectivity, Graph Theory, and Reliable Network Design

I think this is the best introductory text in graph theory I’ve seen that focuses on graph theory. Other treatments will occur in discrete math texts at the collegiate level and include combinatorics, etc, but this one is my preference.

It does contain proofs (the simpler ones), and I encourage readers to really spend some time on them. It covers most major topics in graph theory at an introductory level, but there are some significant practical omissions.

This is meant for undergraduate math majors, so very little on algorithms are discussed. It also discusses embeddings/colorings, etc at a pretty theoretical perspective, which may not be useful to a practicing network engineer. Nonetheless, I recommend at least the first 5 chapters.

This text has more applications of graph theory (besides just network engineering), and is written a bit more casually. That said, I think the treatment is a bit rushed, and the examples tend to focus too much on recreational mathematics, but I’ll at least list it here for people to check out.

Widely considered the first true text on graph theory, this one is a bit more advanced, and quite abstract. It’s meant for mathematicians, but it is the most widely cited.

This text is quite thorough, and though the coding is done in FORTRAN, the premises are not outdated. It's a bit heavy on the linear algebra/matroid theory, so that’s a fair warning.

It does cover shortest-path-algorithms and flow networks, both topics of which are useful to a network engineer, but a solid mathematical background is required. What I do like about this book is its discussion of path algebras, though you would need to understand some concepts in linear/abstract algebra before diving into this general way of looking at path algorithms.

This text is algorithm focused, and written at a more accessible level. The focus is on industrial engineering applications, but the algorithms certainly apply to networking.

Spanning tree, path, and flow algorithms are covered in chapters 2,3, and 4 respectively.

I consider this book pretty widely accessible. The focus is on algorithms and implementation, so if the reader is not comfortable with graph basics, he should accompany this book with another focused on graph theory principles (like Chartrand’s “A First Course in Graph Theory”).

The work covers tree algorithms (spanning tree and maximum branching), path algorithms (shortest path, all shortest path, and k-th shortest path), flow algorithms (ma/min flow, dynamic, gains), matching, and location. The author wrote with an operations researcher in mind, but these algorithms are just as applicable to computer networks.

I included this one for those wanting to look deeper into cyclic interchange and other topics. This book also has a nice chapter on algorithms on graphs, including some routines in FORTRAN, but these can be adapted to other languages as desired.

I wouldn’t recommend this one for basics, but it does cover some interesting topics and applications, particularly for electrical networks. Chapter 3 on trees discusses cyclic interchange. The level of this book is intermediate.

This one also has an OR focus, but is nonetheless worthwhile as a read. This one is significantly more advanced than the first one, but is good for those inclined to theoretical CS and programming in addition to network engineering.

Another advanced algorithms book for those interested in concepts behind these algorithms from a more theoretical perspective. The focus tends to be more on path problems, but this makes another nice extension of (1).

I really can’t recommend this one highly enough as a companion to any of the others and as a great introduction to the space. The survey of topics is fantastic. This one does discuss isomorphism, trees, connectivity, traversability, digraphs, planarity, and distance among other topics in a very readable way, with plenty of motivating examples.