Graph theory Definition and 156 Threads

I'm not sure if this warrants a full post, but I am doing my homework and I came across notation I'm not familiar with. Skimming the chapter it's not in there either. It says "Draw W6" but W6 has a bar over it, like complex conjugate. What does this mean? I know what W6 looks like.

Dear Physics Forum friends, I am a college junior who is currently conducting the undergraduate research in the theoretical computer science. I wrote this post to seek you recommendation on the books that separately treat the graph theory and combinatotics, both in theory and applications. I...

Dear Physics Forum advisers, My recent study on number theory and cryptography got me really interested in the fields of combinatorics and graph theory. I am really interested in learning about them independently now since I will not be able to take the combinatorics course until next year...

Attempt at solution This is an old exam question. Am I correct to say the shortest path goes through M since M is in d(O,M) and d(D,M)? I don't know how to prove this and answer the question about the cost

I constantly find new algorithmic graph theory problems that I need to solve as I work in research. I've learned bits and pieces from google'ing and reinvented the wheel on numerous occasions but it would be nice to get a more standard background. Network science might be more applicable...

Helo everybody, I have buy Introduction to Graph Theory (Dover Books on Mathematics) Book from amazon... Is this book really good? See the pic : https://www.amazon.com/dp/B004TBOGPG/?tag=pfamazon01-20 http://flgopics.science/10/o.png

Hello, I am a student interested in pure mathematics, and am considering giving this book a try. I was wondering what you all think if this book as I have it in my possession. Is it good? If not, is there any very rigorous (I can handle Rudin Analysis rigor) discrete textbook, like one that...

Hey, I'm looking for any books that contain anything on RNA and Graph Theory, was hoping if anyone has any recommendations or can at least point me in the right direction. I've already read through the section on this topic in Goodaire and Parmenter's 'Discrete Mathematics with Graph Theory'...

Homework Statement Prove that all vertices of a complete graph Kn have deg(v) = (n-1) Homework Equations ∑ deg(v) = 2|E| |E| = ½(n)(n-1) for Kn The Attempt at a Solution I may have over thought this but this was my initial path at a formal proof. Using the degree sum formula above and the...

So as I was beginning to read through my Graph Theory textbook I had a burning question I wanted to get some perspective on. So a Graph is defined as an object containing a Vertex Set and an Edge Set, v = # of elements in the vertex set and e = # of elements in the Edge Set (if any) Would...

I want to create graphs where each vertex has three edges, and is connected by these three edges to three distinct vertices. I'd like to know the number of vertices for which this is possible. By playing around a bit, I've found that it's possible for graphs with 4, 8, and 12 vertices. If v is...

Im not entirely sure what section of PF this post should be in so I apologize in advance if this is not in the correct section. I don't know that much graph theory or the various fields that it can be applied to, but I do know that graph theory can be used in social media etc by using dynamic...

I've been doing some light reading on Geometric Graph Theory, and it seem interesting to me. However, at the moment I've only managed to find a few Wikipedia articles and one .PDF of lecture notes. I'm looking for something which is more complete, such as a book or a website for example...

Homework Statement There are n amount of wi-fi networks in a given neighborhood. For every pair that are within 50 yards, the frequency used must be different, otherwise there will be interference. How few frequencies are required so that every wi-fi network can be assigned a frequency without...

Homework Statement Homework, from Modern Graph Theory by Bela Bollobas, section on extremals: 1. Suppose that G is a graph with n > r + 1 vertices and tr(n) + 1 edges. (a) Prove that for every p with r + 1 < p <= n there is a subgraph H of G with |H| = p and e(H) >= tr(p) + 1. [Hint: Try to...

I'm trying to prove that a graph with the below properties has an eulerian path. 1. Graph has no self loops or parallel edges. 2. Every two different vertices u and v have an odd number of common neighbor vertices. I'm thinking about this problem for a whole day and can't manage to prove...

Graph Theory -- Max. Independent set algorithm Homework Statement Design a polynomial time greedy algorithm to compute a maximum independent set for a graph. Explain the algorithm and compute T_w(n). Homework Equations The Attempt at a Solution My terse and informal...

I have the following problem, suppose we have a graph G of n elements, with the property that if we add one missing vertex v, we will get a complete subgraph with s elements K_s of G, in which v belongs to G'. In other words every subgraph of s elements of G is almost a complete graph except for...

Homework Statement Prove that every graph G without isolated vertices has a matching of size at least n(G)/(1+∆(G)). (Hint: Apply induction on e(G)). Homework Equations n(G) = size of the vertex set of G and ∆(G)= maximum degree of v in G The Attempt at a Solution For the base...

Homework Statement Prove that if a graph has > (n-1)(n-2) /2 edges, it is connected. Homework Equations ?? The Attempt at a Solution I've drawn several examples and made tables, and I can see that the graph is indeed connected if it has more edges than [(n-1)(n-2)]/2. But...

Hi All, I am contemplating which graph theory text to purchase. I am stuck between a) Graph Theory by Bondy and Murty B) Graph Theory by Richard Diestel I have already been through Trudeau's intro text on my own and am looking for something deeper and more advanced. I am...

Homework Statement All vertices in a closed trail have even degree. Homework Equations The Attempt at a Solution Intuitively, I know this statement is true, but I can't seem to see a clear way to show it. I know that a closed trail is a path that connects vertices, so one would follow an...

Homework Statement Use ordinary induction on k or on the number of edges (one by one) to prove that a connected graph with 2k odd vertices composes into k trails if k > 0. Does this remain true without the connectedness hypothesis? Homework Equations The Attempt at a Solution If k...

I have these problems I need help with. Can anyone take a look at them? https://www.dropbox.com/s/vq8rk6z5ea5gpwd/Problems.docx

Hello, Just wondering if any of you have encountered a term for a particular type of graph. It is like a graph that allows for loops, but for loops, instead of joining a vertex to itself, it joins a vertex to nothing. I just want to be consistent with existing terminology, if there are none...

Please check if my two following proofs are correct. I didn't know whether it was better to post them in a separate thread or not. I posted them together since they are both questions related to graph theory. Let me know if I should have separated them. Prove that a graph G is a tree iff it has...

Prove that a graph on v vertices that has no cycle is connected iff it has precisely v-1 edges. Necessary Condition: A connected graph with no cycles is a tree. Therefore, it has v-1 edges. Sufficient Condition: I need help with this. How can I use "a connected graph has no cycles iff it has...

[SOLVED]Graph theory proof The graph G has precisely two vertices x and y of odd degree. A new graph of multigraph H is formed from G by adding an edge xy. If H is connected, prove that G is connected. Please check my following proof for this problem. Since G has exactly two odd vertices...

I am currently taking a combinatorics class that surveys a little bit of graph theory and it piqued my interest. Does anyone have a recommendation for a good introductory book on the subject? I am really interested in finding a book that is very readable and not the standard definition, lemma...

Homework Statement Hey guys, I have this question. Given a tree T = (V , F), find an algorithm which finds u in V, so in the graph T = (V \ {u} , F) the size of each connected component is |V| / 2 at most. What is the complexity? Homework Equations The Attempt at a Solution...

Can anyone comment on the advantages and disadvantages of both graph theory vs. using a system of differential equations to study a complex network? For example, how much computing power and running time would a graph theory approach use compared to say solving a system of 100 differential...

Hi I was reading a project description for a graph theory REU and I got stuck on a sentence I couldn't understand. Here is the description and I've bolded the part I don't get. Does this mean to remove vertices from the "other graph" until you've broken it up to G1, G2, and G3 (and maybe...

Hello everybody! I am a real amateur in Combinatorics. So please answer in the most basic way! ============================================= 1- Suppose for a graph G we have Delta=max(deg Vi : 1<=i<=n). If Delta<=2, prove that the graph G is made up of Paths and Cycles. 2- Suppose G is a...

Let's say I had a network of enzymes that are all interconnected that may be involved in cancer progression. Each enzyme produces a chemical product that might be used by some other member in this network, but each enzyme might produce a product at different rates. Is there a way I could...

Hello everyone, I'm studying basic graph theory, and my instructor gives me these statements to translate into pictures. I don't quite understand the meanings of the statements, but I have some thoughts about them. 1/ "Any two vertices a, b are connected by at least 2 distinct paths of...

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?

I am thinking about this problem that come up in some of my work, I think this has been solved before, though I am not aware where I could find the solution. Here is the question: Suppose a graph has say 20 nodes with no edge initially, and at each instance, 4 (different) nodes are randomly...

Theorem: Prove that there exist $n$ edge disjoint Hamiltonian cycles in the complete graph $K_{2n+1}$. ---------------------------------------------------------------------------------- I have found two constructive proofs of this over the internet. But I would like to prove it...

Homework Statement A house has been framed and now several jobs remain to be done. Electrical wiring must be installed, a roof must be added, drywall must be put up and it must be painted, and flooring must be installed. The electrical work must be done before the drywalling, and the drywall...

Hi all, I don't know if analysis is the right place for me to post this thread therefore please accept my apologies in advance if I am mistaken. In graph theory the incidence function that associates vertices & edges http://img41.imageshack.us/img41/8171/32004284.jpg , in the text it has...

If I have a very large graph (set of edges and vertices, NOT the "picture/sketch" of the graph), what is a very efficient way to find all the vertices with only one edge attached to them. Most of the vertices will have many edges attached to them. Also any vertex may be connected to itself...

The problem is as follows: --------------------------------------------------------------------------------------------------------------------------------- Let G be a connected graph. For a vertex x of G we denote by G−x the graph formed by removing x and all edges incident on x from G. G is...

Hello everyone. All help appreciated.

I'm curious. Do you think that it is better to go into a subject like graph theory than it is to go into algebra, in the sense of research prospects. Graph theory, at the moment, is much much more active of an area than algebra. It seems also that going into a subject that requires you to more...

Hi everyone, Any help would be appreciated.

Hi everyone. I know this holds for complete graphs, I've proved that by induction. But how can I prove it for graphs which aren't complete? And what is the significance of (2n+1)/3? If a vertex has that degree, does it have some property I should immediately spot?

(There isn't a section for Graph Theory, so I figured I'd post this in a spot where a lot of pure math topics are posted). Looking for an easy to read introduction to graph theory book to prep me for a course I'll be taking in the Spring. Nothing too simple, but nothing too in depth (as...

I'm looking for an introductory book on graph theory. I'll be taking a course in graph theory this Spring so I don't want anything too technical, just something to get my feet wet. any recommendations for an easy to follow engaging book? A "for dummies" if you will.

Some background: my friends love to confound me with nonsensical questions, because they know I'm the type of person who cannot let a question go, even if it has no answer, and when I arrive at one, it will be so rigidly logical that no matter how ridiculous it sounds it must be correct. My...

A school class has 90 students, each of whom has ten friends among the other students. Prove that each student can invite three people at a restaurant so that each of the four people at the table will know at least two of the other three. If this had to be translated to a graph it would...