Let G be a k-connected graph with k greater than 1. The longest cycles in G share at least k vertices.

This is the problem I am working on for a research project. I am correctly doing an independent investigation of the case k = 3 so that I can get a feel for the problem. I was wondering.. what can we say about a longest cycle in a graph? What kind of properties does a longest cycle have?

How about longest paths? What can be said about the longest path in a k-connected graph?

Let G be a k-connected graph with k greater than 1. The longest cycles in G share at least k vertices.

This is the problem I am working on for a research project. I am correctly doing an independent investigation of the case k = 3 so that I can get a feel for the problem. I was wondering.. what can we say about a longest cycle in a graph? What kind of properties does a longest cycle have?
...Some of us are older physicists, educated before physics became mainly math. I am guessing a "cycle" in some function (and it graph) is defined by something like F(x) = F(x+n) for all x where n may be the "length of the cycle" (along the x-axis)*. However, perhaps the range, not n, is the "length of the cycle." I.e. all the distance from X1 to X2 (where X1<X2) within which
f(x) = f(x+n) is valid for some fixed n.


I less confidently guess that the "longest cycle" is the greatest value of n. I.e. I can imagine a function which in part of its range n = 3 and f(x) in this sub range has same value as f(x+3) and then in some other part of the defined range f(x) = f(x+5) so n = 5 would be a "longer range," (or longer cycle?) perhaps the longest.

With still less confidence I guess a "vertice" of the graph is a point where the slope changes from positive to negative (or conversly) - I.e. the vertices divide the full graph up into monotonic sub-graph sections.

Please confirm or correct these guesses.

I have not the slightest idea what the "k-connected" is all about. Is it possible to tell a very ignorant, but not extremely dumb, physicist what this problem is, in terms he can understand?

I assure you, that if you are so kind, I will not help you solve your problem, :D but more activity in this thread may attract math whizes like D H who may be able to. (I have noticed that threads with zero replies often sit for a long time, so I am doing what I can to help you.)
------------------
*I sure hope you are not speaking of the "arc length" along the graph - if you are that is more proof that some mathematicians are in deed as "pathological" as their functions. :eek:

Some of us are older physicists, educated before physics became mainly math. I am guessing a "cycle" in some function (and it graph) is defined by something like F(x) = F(x+n) for all x where n may be the "length of the cycle" (along the x-axis)*. However, perhaps the range, not n, is the "length of the cycle." I.e. all the distance from X1 to X2 (where X1<X2) within which
f(x) = f(x+n) is valid for some fixed n.

By graph, I mean something like this:

http://www.geom.uiuc.edu/~zarembe/graph6.gif

What you are talking about is the "graph" of a function. I just mean that I have a set of vertices (finite) and a set of edges that connect one vertex to another.

K=3

1=90
2=180
3=270
4=360

360=1

4=1

3<1

Yeah not exactly calculus.
Not sure how you would put that into an equation.

And I have no idea what you are talking about, but I do know that this has nothing to do with the problem.

OK - should I assume that your lines between verticies, if not already in a 2D plane, can be projected down onto a 2D plane without changing the topographical description of the"graph"? I.e. no new vertices made or old ones falling at the same point in the 2D plane? I.e you are interested in a 2D problem only.

On the "k-connected" idea, perhaps I can understand if you tell its value (and a few words) about how "k-connected are:
(1)triangle = three lines between three verticies
(2)square with both diagonals = 5 verticies and I think 8 lines if only the topography is important (I.e. when the "diagonals" are "bent" to not cross in the center of the square, surely we then have four distinct "internal lines" and four distinct "permiter lines" so even with "straight diagonals" inside I would count them as four lines (Not two)

Now for some curves ;) (also test if you consider curve and straight line between same two verticies as "degenerate line pair", only one line, or two "lines" if you tell me the number of lines.)

(3) purely convex, but fully irregular* hexagon perfectly (and maximally) inscribed in perfect circle.
(4) same as (3) but with 5 internal lines all leaving one of the verticies and each terminating on different one of the others.
------------
* I.e. none of the 6 sides are parallel to any other. - I love this figure as the intersections of lines 1&4, 2&5 3&6 define three points, A, B, and C.
Amazingly A, B & C always fall on the same straight line! (For me, it is a geometric example of "order out of chaos.")

That is enough for now. I am sure I will be back with more questions trying to understand the "k-connected" concept.

BTW In you graph illustration (post 3) at each of what surely must be the "verticies" you have a small circle. Is that only calling attention to the vertice - like a place to write its name (a, b, c, .... etc.) in or is it a curved lines that happens to begin and end on the same vertice? If not intended as a line, can a "line" begin and end on the same vertice? (obviously a straight line can not.) Is the simplist "graph" a ray from the origin to infinity? (one line and one vertice) Or is thart not quite a "graph" Or is it the simplest graph but has two verticies? (second at infinity)?

OK - should I assume that your lines between verticies, if not already in a 2D plane, can be projected down onto a 2D plane without changing the topographical description of the"graph"? I.e. no new vertices made or old ones falling at the same point in the 2D plane? I.e you are interested in a 2D problem only.

Graph theory is, for the most part, only concerned with 2D graphs. As a matter of fact, dimension does not really play a part in graph theory since we are only concerned with the properties of the graph and not how it really looks. One exception might be something like the 3-services problem.

On the "k-connected" idea, perhaps I can understand if you tell its value (and a few words) about how "k-connected are:
(1)triangle = three lines between three verticies
(2)square with both diagonals = 5 verticies and I think 8 lines if only the topography is important (I.e. when the "diagonals" are "bent" to not cross in the center of the square, surely we then have four distinct "internal lines" and four distinct "permiter lines" so even with "straight diagonals" inside I would count them as four lines (Not two)

By k-connected, I mean something like this:

Given a graph G, there is a MINIMUM set (not necessarily unique) S, subset of the V (vertices), such that G-V is disconnected. By disconnected we mean the graph is seperated into at least 2 parts. For example, if we have the 4 vetices and 4 edges and connect them in such a way that it looks like a square, it's connectivity is 2. A graph is k-connected if |S|>=k. So if a graph 's connectivity is 10, then the graph is 10-connected, 9-connect, 8-connected, ... , 1-connected. When we talk about connectivity, we are referring to a graph that is not already in 2 components.

Now for some curves ;) (also test if you consider curve and straight line between same two verticies as "degenerate line pair", only one line, or two "lines" if you tell me the number of lines.)

The "shape" of a edge in a graph does not matter. All that matters is whether a vertex is connected to another one or not... and what kinds of properties these two share with other vertices.

I think you are confusing what I mean by graph. Refer to this: http://en.wikipedia.org/wiki/Graph_theory

BTW In you graph illustration (post 3) at each of what surely must be the "verticies" you have a small circle. Is that only calling attention to the vertice - like a place to write its name (a, b, c, .... etc.) in or is it a curved lines that happens to begin and end on the same vertice? If not intended as a line, can a "line" begin and end on the same vertice? (obviously a straight line can not.) Is the simplist "graph" a ray from the origin to infinity? (one line and one vertice) Or is thart not quite a "graph" Or is it the simplest graph but has two verticies? (second at infinity)?

The vertices are big just to call attention to them.

Oh, and sorry if I am just confusing. I am on some...err... ADD meds.

Thanks both link and text. I am starting to get some understanding of "k-conectivity" At my stazge of ignorance, it seems graph theory is a simplification of topology in that surfaces do not exist and graph are generally concerned only with 2D sets of vereticies and connections between them.

It now seems to me that "k-connectivity" is just answering the question:
What is the least number of lines (connections between pairs of verticies) that must be cut (removed) to break the graph into two separate pieces?

I think, that graph G1 with only 4 verticies (for example at corners of a square or any convex figure) can have six lines (or connections) if both "diagonals" are present but their crossing within the square (essential in 2D, but not with a 3D "bent square") does not constitute / create a fifth vertice.
To separate G1 into two parts, G1a & G1b, three cuts (k = 3) are required if a single isolated "lineless" vertice is considered a graph, but if all graphs must have aty least one line (as I suspect) then k = 4 and the resulting G1a = G1b. (both have two verticies and one line) Which is it?

I am not still clear if 6 lines is the max possible with only 4 verticies, A,B,C & D. For example, if these four vertices fall on a circle, which is part of the graph G2, it seems that the verticies are also connected by "arcs" ab, bc, cd, & da as well as straight AB, BC, CD, DA, AC, & BD.

You (and your link) did not answer my "curve questions" fully, so I do not know if arc line ab is distinct in "graph theory" from straight line AB. If it is and all graphs must have at least one line, then for G2 k= 6, but only 5 if isolated lineless vertice is a "graph."

Can you clarify these two points (and correct me if needed)?

Note if ab is not the same as AB, in graph theory, then k can be arbitarly large for G3, which has only two verticies, so I am betting that ab = AB in graph theory as it does in 2D "hole-less surface" topology, (because path ab can be deformed into path AB without leaving the surface). However in the 3D hole-less SURFACE of a donut there are two distinct topological paths ab and AB between points A & B. - Part of why I suspect that "graph theory" may be just a sub set of topology.

Again I thank you for comments.

Thanks both link and text. I am starting to get some understanding of "k-conectivity" At my stazge of ignorance, it seems graph theory is a simplification of topology in that surfaces do not exist and graph are generally concerned only with 2D sets of vereticies and connections between them.

It now seems to me that "k-connectivity" is just answering the question:
What is the least number of lines (connections between pairs of verticies) that must be cut (removed) to break the graph into two separate pieces?

I think, that graph G1 with only 4 verticies (for example at corners of a square or any convex figure) can have six lines (or connections) if both "diagonals" are present but their crossing within the square (essential in 2D, but not with a 3D "bent square") does not constitute / create a fifth vertice.
To separate G1 into two parts, G1a & G1b, three cuts (k = 3) are required if a single isolated "lineless" vertice is considered a graph, but if all graphs must have aty least one line (as I suspect) then k = 4 and the resulting G1a = G1b. (both have two verticies and one line) Which is it?

I am not still clear if 6 lines is the max possible with only 4 verticies, A,B,C & D. For example, if these four vertices fall on a circle, which is part of the graph G2, it seems that the verticies are also connected by "arcs" ab, bc, cd, & da as well as straight AB, BC, CD, DA, AC, & BD.

You (and your link) did not answer my "curve questions" fully, so I do not know if arc line ab is distinct in "graph theory" from straight line AB. If it is and all graphs must have at least one line, then for G2 k= 6, but only 5 if isolated lineless vertice is a "graph."

Can you clarify these two points (and correct me if needed)?

Note if ab is not the same as AB, in graph theory, then k can be arbitarly large for G3, which has only two verticies, so I am betting that ab = AB in graph theory as it does in 2D "hole-less surface" topology, (because path ab can be deformed into path AB without leaving the surface). However in the 3D hole-less SURFACE of a donut there are two distinct topological paths ab and AB between points A & B. - Part of why I suspect that "graph theory" may be just a sub set of topology.

Again I thank you for comments.

Billy you just said what I wanted to say but didn't know how.

Thanks.

-Klippy

Thanks both link and text. I am starting to get some understanding of "k-conectivity" At my stazge of ignorance, it seems graph theory is a simplification of topology in that surfaces do not exist and graph are generally concerned only with 2D sets of vereticies and connections between them.

Sure.. I guess.

It now seems to me that "k-connectivity" is just answering the question:
What is the least number of lines (connections between pairs of verticies) that must be cut (removed) to break the graph into two separate pieces?

Well you are describing Edge connectivity. I am talking about vertex connectivity. Also, removing certain edges can make the graph disconnect into more than 2 commonents.

If G is a graph, k(G) is defined to be the minimum number of vertices required to seperate the graph into 2 or more components. A graph is said to be k-connected if k <= k(G).

You (and your link) did not answer my "curve questions" fully, so I do not know if arc line ab is distinct in "graph theory" from straight line AB. If it is and all graphs must have at least one line, then for G2 k= 6, but only 5 if isolated lineless vertice is a "graph."

http://i64.photobucket.com/albums/h197/absane/graph.png

The two graphs are isomorphic... you can even say it's the same graph. How the edges are drawn does not matter. The definition of a graph concerns itself only with vertices and if they are connected to each other or not (pairwise).

Sure.. I guess.



Well you are describing Edge connectivity. I am talking about vertex connectivity. Also, removing certain edges can make the graph disconnect into more than 2 commonents.

If G is a graph, k(G) is defined to be the minimum number of vertices required to seperate the graph into 2 or more components. A graph is said to be k-connected if k <= k(G).



http://i64.photobucket.com/albums/h197/absane/graph.png


The two graphs are isomorphic... you can even say it's the same graph. How the edges are drawn does not matter. The definition of a graph concerns itself only with vertices and if they are connected to each other or not (pairwise).

I don't understand. What's the point of this? What practical purpose would you ever use this for?

I don't understand. What's the point of this? What practical purpose would you ever use this for?

Computer science is just one example. The efficiency of networks and Internet relies on graph theory. Also, the military uses it for communications between missiles.

And what does it matter what is the use? Do I need a reason to study this?

I don't seem to get clear answer to twice asked question (related to k-connectivity).

I can cut off a vertice buy cutting all lines terminating on it, but is that isolated, "lineless" vertice a "graph" (I suspect all graphs must have at least two verticies and a line connecting them, but want to confirm this.)

I don't seem to get clear answer to twice asked question (related to k-connectivity).

I can cut off a vertice buy cutting all lines terminating on it, but is that isolated, "lineless" vertice a "graph" (I suspect all graphs must have at least two verticies and a line connecting them, but want to confirm this.)

I guess I don't understand where you are coming from.. because the terminology is too clear to me.

An edge only exists if there are 2 vertices for it to connect to. You cannot have some "stray edge."

If you remove all the edges from a vertex, then you have that vertex "by itself." The vertex still remains. However, if you remove a vertex from the graph, then all the edges incident to it are deleted from the edge set.

There are two things though: vertex connectivity and edge connectivity. I am only concerned with vertex connectivity.

I guess I don't understand where you are coming from.. because the terminology is too clear to me....see again my post 4 to understand "where I am coming from" For example my example (1) a simple triangle, (three lines and three verticies.) If cut the two lines coming to one of the verticies (obviously they must), I then have a graph conisting of two vericies joined by a line and an isolated "lineless" vertice
It is a question of definition as to whether or not that "lineless" vertice is "a graph." If it is not, then does any "k" exist for this "triangle graph"?

If you have time, please look at my questions relating to my post 4 examples (2), (3), & (4). especially (3) as another question (definition related also) has to do with more than one line (in drawing of it at least) between the two same vetricies. In that (3) example every pair of vertice has a arc and also a straght line in the graph connecting them; but perhaps there are only 6 lines total as you do not consider the arc and the straight line as distinct connections. Here I am trying to understand what is a "line."

If there is only 6 lines, then it seems that applictions of "graph theory" to a communication net with redundant connections is not possible. If however in my example (3) of post 4 there are 12 lines, it would be applicable to that communication net, but then there is some meaning to the "shape of the line."

The reference you gave just named lines by telling their terminal verticies. If there are two lines (an arc and a straight line, in my example 3 between vertices A & B,) then the notaion of these two line could be AB1 & AB2.

It is all clear to you as you already know the definitions of what is a "graph" and what is a "line", but I obviously do not. I have given examples for you to clarify.

Specificially are there 6 or 12 lines in my example (3) of post (4) - If you just answer that and tell if a "lineless" vertice is, or is not, "a graph" it would advance my understanding greatly. (Help me formulate working definitions of "graph" and "line") Your responces are as if you never read post (4).

A graph is normally defined as the pair of two sets: V the set of vertices, and E the set of edges. An edge is just a pair of vertices. If you differentiate between the pair (a,b) and (b,a), where a and b are vertices, then the graph is called directed and otherwise it is called undirected. You can represent an undirected graph by appropriately drawing points for vertices and lines (or curves) for edges. It does not matter how you draw these lines or points, the graph 'behind' this picture is the same. Then for a directed graph you can draw edges with arrows, the arrow of an edge (a,b) pointing towards the vertex b.

Your Examples (1) and (2) are complete graphs, i.e., the edge sets of those graphs consists of every possible pair of verices. Therefore, no matter how many vertices you remove the graph remains connected as long as it is not empty. Since this is a special situation, by convention the connectivity of the complete graph with n vertices is n-1. It is the same as agreeing that a graph with only one vertex is disconnected.

For Example (3), you can remove 2 vertices and render the graph disconnected, and removing any one of the vertices will not make the graph disconnected; so the connectivity is 2. The graph is k-connected for any k greater or equal to 2.

It seems that Example (4) does not define a graph uniquely, you have to specify exactly which five of the diagonals you are considering.

Typically loops (an edge with the same vertex as its two ends) and multiple edges (more than one edges connecting two vertices) are not allowed for graphs, but there are variations in the definitions. These types of graphs are sometimes called multigraphs.

To Temur: Thanks, that was clear and now I know what the basic elements of graph theory are.

I assume I was correct that conventional graph theory is of little use in a communication network (like the internet) which is highly multi-path interconnected. Aslo that if one does want to study it with "multigraph theory" the concepts of directed and undirected still apply. For example the telephone line in my house (vertice H) and the local switching station (vertice S) which has a copper wire connecting to H is bi-directional so there is no difference between SH and HS edge; but the TV program which comes to my house (thru several vertices) from the very distant BBC studio (vertice B) is directed as only B....H exists (no H.....B)

Is this "Path Notation" I just invented, common (or totally useless as in any ONE graph all verticies pair always have a "connection path"? I suspect that it might have some use in directed graphs. For example B....H and H....B might be extremely different. I.e. only have their terminal verticies in common.
Often even in the directed multigraph case, B....H is not well specfied (as you pointed out for my example 4 in post 4) because many different intermedicate verticies will exist. An every day example of a directed multi-graph, of interest to everyone is a city with one-way streets.

In someways, the concept of "k-connected" in that "city case" is related to the old joke (A reply to someone asking for directions to the airport etc.): "You can't get there from here."

Just to remove the ambiguity in my graph (G4) example (4) of post 4, I designate the 6 vetricies as a,b,c,d,e, & f, in cyclic clockwise order around the circle. It is an undirected "multi-graph" in that ab1, and ab2 (the line and the arc respectively) BOTH exist but ab1 = ba1, etc. (likewise for bc1,bc2; cd1,cd2; de1,de2, ef1,ef2; and fa1,fa2) as "edges" plus G4 has ac, ad, & ae but I am not sure these last three are called "edges." Perhaps they are "internal lines" (not "edges")? If that is the case, then the 6 xy1 are also "internal lines" (Only the 6 xy2 arcs are edges.)

In a simple graph (not a "multi-graph") all connections are "edges" (almost sure) as then there is not even a hint of a "shape concept." I.e. it is totally defined by a complete table of the connections existing.

If a "non-edges" concept exist with multi-graphs, which must have at least a hint of a "shape concept," is there a standard notation (convention) for "edges" and "non-edges"?

For example, using my now fully defined G4 of post 4, the arc AB2 is an edge, while straight lines ab1 and ac are not. (I.e. Capitals use for "edges" and lower case for "non-edges" in my convention just invented.)

PS Thanks also for opening my eyes to the concept of complete vs incomplete graphs.

I assume I was correct that conventional graph theory is of little use in a communication network (like the internet) which is highly multi-path interconnected.

Conventional graph theory alows you to have multiple paths between two nodes, the only thing it forbids is to have multiple edges between two nodes. Edge is the 'direct connection' between two nodes, while path can consist of a sequence of many edges. Since internet is a node-to-node (not sure about terminology) network, it perfectly fits in conventional graph theory, at least when you describe the topology of the network.


Aslo that if one does want to study it with "multigraph theory" the concepts of directed and undirected still apply. For example the telephone line in my house (vertice H) and the local switching station (vertice S) which has a copper wire connecting to H is bi-directional so there is no difference between SH and HS edge; but the TV program which comes to my house (thru several vertices) from the very distant BBC studio (vertice B) is directed as only B....H exists (no H.....B)

Is this "Path Notation" I just invented, common (or totally useless as in any ONE graph all verticies pair always have a "connection path"? I suspect that it might have some use in directed graphs. For example B....H and H....B might be extremely different. I.e. only have their terminal verticies in common.


You are right, and this notation is used for paths. It is not useless, since it conveys the information exactly which vertices are along the path, while the fact that all pairs have a "connection path" will not give you such information.

I want to make it clear that it is not true that in any ONE graph all verticies pair always have a "connection path". What you mean by ONE graph is probably one connected component of a graph. A graph can consist of subgraphs which are not interconnected. The notion of connectivity is closely related to this: you try to remove minimum number of vertices and render the graph disconnected, latter meaning that there are at least two vertices in the graph such that there is no "connection path" between them.


Often even in the directed multigraph case, B....H is not well specfied (as you pointed out for my example 4 in post 4) because many different intermedicate verticies will exist. An every day example of a directed multi-graph, of interest to everyone is a city with one-way streets.

In someways, the concept of "k-connected" in that "city case" is related to the old joke (A reply to someone asking for directions to the airport etc.): "You can't get there from here."

Just to remove the ambiguity in my graph (G4) example (4) of post 4, I designate the 6 vetricies as a,b,c,d,e, & f, in cyclic clockwise order around the circle. It is an undirected "multi-graph" in that ab1, and ab2 (the line and the arc respectively) BOTH exist but ab1 = ba1, etc. (likewise for bc1,bc2; cd1,cd2; de1,de2, ef1,ef2; and fa1,fa2) as "edges" plus G4 has ac, ad, & ae but I am not sure these last three are called "edges." Perhaps they are "internal lines" (not "edges")? If that is the case, then the 6 xy1 are also "internal lines" (Only the 6 xy2 arcs are edges.)


By appropriately defining vertices you can make a graph (not multigraph) out of the city. For example, suppose that points A and B are connected by two different roads, with no one vertex in the middle of any of these two roads. Then originally there are two different edges connecting A and B. Now you just take some artificial point C on one of the roads, and make C a vertex of the graph. By introducing this additional vertex, the graph is at least "locally" not a multigraph, since one of the edges connecting A and B is replaced by the path ACB (presence of C makes it no longer an edge).


In a simple graph (not a "multi-graph") all connections are "edges" (almost sure) as then there is not even a hint of a "shape concept." I.e. it is totally defined by a complete table of the connections existing.


You are absolutely right.


If a "non-edges" concept exist with multi-graphs, which must have at least a hint of a "shape concept," is there a standard notation (convention) for "edges" and "non-edges"?

For example, using my now fully defined G4 of post 4, the arc AB2 is an edge, while straight lines ab1 and ac are not. (I.e. Capitals use for "edges" and lower case for "non-edges" in my convention just invented.)


Can you clarify a bit more about what you mean by "non-edges"?

Thanks again.Conventional graph theory... forbids ... multiple edges between two nodes. Edge is the 'direct connection' between two nodes, while path can consist of a sequence of many edges. ...OK, I was confused by lay idea that edge was sort of the perimeter of the graph or at least not any line with a path all the way around it. (why in post 15 I spoke of "non edges."

As I now understand it all lines between any two verticies are "edges" in standard graph theory (but think in "multi-graph theory", a pair of vertices can have more than one edge eg. AB1 & AB2 so there must be some "shape" idea or some thing distinguishing them.

In both std and multi-graph theory there can be two edges if at least one is directed as that would be a distinguishing characteristic. AB not same as BA, but, if it is possible that AB is bi-directional while BA is not, I do not know what the notation for that would be.
I want to make it clear that it is not true that in any ONE graph all verticies pair always have a "connection path". What you mean by ONE graph is probably one connected component of a graph. A graph can consist of subgraphs which are not interconnected. The notion of connectivity is closely related to this: you try to remove minimum number of vertices and render the graph disconnected, latter meaning that there are at least two vertices in the graph such that there is no "connection path" between them.Again I had wrong idea, as you guessed. If "one graph" can consist of two or more unconnected sub graphs, is k for it necessarily zero? (but one can speak of non-zero K for each of the sub graphs, I assume)

On your last "city comments" in essence you are saying, I think, that if all street intersections are vertices and no different direct paths between any two vertices exist (except for pairs of one way streets) then the city is a graph of the standard graph theory.