Graph product - Revision history

en>Michael Hardy: deleting the "stub" tag

2014-12-16T18:16:45Z

deleting the "stub" tag

← Older revision		Revision as of 20:16, 16 December 2014
Line 1:		Line 1:
	~~Hello, my~~ title ~~is Andrew and~~ my ~~spouse doesn~~'~~t like~~ it ~~at all~~. ~~One of the extremely very best issues~~ in ~~the world for him~~ is performing ballet ~~and he'll be beginning some thing else along with it. She functions as a travel agent~~ but ~~soon she'll be on her own. For a while~~ I've been ~~in Alaska but I will have to move in a good psychic ([http://kard.dk/?p=24252 kard.dk]) year or two~~.<br><br>~~Also visit~~ my blog post [http://~~www~~.~~taehyuna~~.~~net~~/xe/~~?document_srl=78721~~ psychic ~~readings online] ([http://gcjcteam.org/index.php?mid=etc_video&document_srl=696611&sort_index=regdate&order_type=desc mouse click the up coming webpage~~])		Hi there. My name is Sophia Meagher even though it is not the title on my beginning certificate. Since he was eighteen he's been working as an info officer but he plans on changing it. Her family members lives in Ohio. What me and my family adore is performing ballet but I've been using on new things recently.<br><br>my blog post ... [http://165.132.39.93/xe/visitors/372912 clairvoyant psychic]

en>BG19bot: WP:CHECKWIKI error fix for #02. Fix br tag, Do general fixes if a problem exists. - using AWB (9949)

2014-02-28T18:44:05Z

WP:CHECKWIKI error fix for #02. Fix br tag, Do general fixes if a problem exists. - using AWB (9949)

← Older revision		Revision as of 20:44, 28 February 2014
Line 1:		Line 1:
	~~[[Image:threshold graph.png\|thumb\|240px\|An example of a threshold graph.]]~~		Hello, my title is Andrew and my spouse doesn't like it at all. One of the extremely very best issues in the world for him is performing ballet and he'll be beginning some thing else along with it. She functions as a travel agent but soon she'll be on her own. For a while I've been in Alaska but I will have to move in a good psychic ([http://kard.dk/?p=24252 kard.dk]) year or two.<br><br>Also visit my blog post [http://www.taehyuna.net/xe/?document_srl=78721 psychic readings online] ([http://gcjcteam.org/index.php?mid=etc_video&document_srl=696611&sort_index=regdate&order_type=desc mouse click the up coming webpage])
	~~In [[graph theory]]~~, a '~~''threshold graph''' is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:~~
	~~#Addition of a single isolated vertex to the graph.~~
	~~#Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to~~ all ~~other vertices~~.

	~~For example, the graph~~ of the ~~figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices,~~ in the ~~order in which they are numbered.~~

	Threshold graphs were first introduced by {{harvtxt\|Chvátal\|Hammer\|1977}}. A chapter on threshold graphs appears in {{harvtxt\|Golumbic\|1980}}, and the book {{harvtxt\|Mahadev\|Peled\|1995}} is devoted to them.

	~~== Alternative definitions ==~~

	~~An equivalent definition is the following: a graph is a threshold graph if there are a real number <math>S</math> and~~ for ~~each vertex <math>v</math> a real vertex weight <math>w(v)</math> such that for any two vertices <math>v,u</math>, <math>uv</math>~~ is ~~an edge if~~ and ~~only if <math>w(u)+w(v)\ge S</math>~~.
	~~<!-- To see why the two definition are equivalent, observe that~~ a graph constructed using the first definition is also a graph of the second definition by setting <math>S=1</math>, <math>w(u)=1</math> for vertices that were added as dominating vertices and <math>w(u)=0</math> for all other vertices. For the other direction, given <math>S</math> and <math>w</math> we can construct the same graph by starting with the graph whose only vertex is the vertex with the minimum weight and then examining all remaining vertices in ~~order of non-decreasing weight. Each one is added as~~ a ~~-->~~

	~~Another equivalent definition is this:~~ ~~a graph is a threshold graph if there are a real number <math>T</math> and for each vertex <math>v</math> a real vertex weight <math>a~~(~~v)<~~/~~math> such that for any vertex set <math>X\subseteq V<~~/~~math>, <math>X</math> is independent if and only if <math>\sum_{v \in X} a(v) \ge T~~.</~~math>~~

	~~The name "threshold graph" comes from these definitions: ''S'' is the "threshold" for the property of being an edge, or equivalently ''T'' is the threshold for being independent.~~

	~~==Decomposition=~~=
	~~From the definition which uses repeated addition of vertices, one can derive an alternative way of uniquely describing a threshold graph, by means of a string of symbols~~. <math>\epsilon</math> is always the first character of the string, and represents the first vertex of the graph. Every subsequent character is either <math>u</math>, which denotes the addition of an isolated vertex (or ''union'' vertex), or ~~<math>j</math>, which denotes the addition of a dominating vertex (or ''join'' vertex)~~. ~~For example, the string~~ <~~math~~>~~\epsilon u u j~~<~~/math~~> ~~represents a star graph with three leaves, while <math>\epsilon u j<~~/~~math> represents a path on three vertices. The graph of the figure can be represented as <math>\epsilon uuujuuj <~~/~~math>~~

	~~==Related classes of graphs==~~
	~~Threshold graphs are a special case of [[cograph]]s, [[split graph]]s, and [[trivially perfect graph]]s~~. ~~Every graph that is both a cograph and a split graph is a threshold graph~~. Every graph that is both a trivially perfect graph and the [[Complement graph\|complementary graph]] of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of [[interval graph]]s.

	~~==See also=~~=
	*[[Series-parallel graph]]

	~~==References==~~
	*{{citation
	~~\| last1 = Chvátal \| first1 = Václav \| author1-link = Václav Chvátal~~
	~~\| last2 = Hammer \| first2 = Peter L. \| author2-link = Peter Hammer~~
	~~\| contribution = Aggregation of inequalities in integer programming~~
	~~\| editor1-last = Hammer \| editor1-first = P. L.~~
	~~\| editor2-last = Johnson \| editor2-first = E. L.~~
	~~\| editor3-last = Korte \| editor3-first = B. H.~~
	~~\| editor4-last = Nemhauser \| editor4-first = G. L.~~
	~~\| location = Amsterdam~~
	~~\| pages = 145–162~~
	~~\| publisher = North-Holland~~
	~~\| series = Annals of Discrete Mathematics~~
	~~\| title = Studies in Integer Programming~~ (~~Proc. Worksh. Bonn 1975)~~
	~~\| volume = 1~~
	~~\| year = 1977}}.~~
	*{{citation
	~~\| last = Golumbic \| first = Martin Charles \| author-link = Martin Charles Golumbic~~
	~~\| location = New York~~
	~~\| publisher = Academic Press~~
	~~\| title = Algorithmic Graph Theory and Perfect Graphs~~
	~~\| year = 1980}}. 2nd edition, Annals of Discrete Mathematics, '''57''', Elsevier, 2004.~~
	*{{citation
	~~\| last1 = Mahadev \| first1 = N. V. R.~~
	~~\| last2 = Peled \| first2 = Uri N.~~
	~~\| publisher = Elsevier~~
	~~\| title = Threshold Graphs and Related Topics~~
	~~\| year = 1995}}.~~

	~~==External links==~~
	*[http://~~wwwteo.informatik~~.~~uni-rostock.de~~/~~isgci/classes/gc_328~~.~~html Threshold graphs], Information System on Graph Class Inclusions, Univ. of Rostock.~~

	~~{{DEFAULTSORT:Threshold Graph}}~~
	~~[[Category:Graph families]]~~
	~~[[Category:Perfect graphs]~~]

en>Mark viking: Added wl

2013-09-20T03:47:42Z

Added wl

← Older revision		Revision as of 05:47, 20 September 2013
Line 1:		Line 1:
	~~The writer~~'~~s title~~ is ~~Andera and she believes it sounds fairly great~~. For a ~~while I've been~~ in ~~Alaska but [http~~://~~www~~.~~onbizin~~.~~co.kr~~/xe/~~?document_srl=320614 online psychic chat] I will have to move~~ in a ~~yr or two. Office supervising~~ is ~~what she does~~ for a ~~residing. Playing badminton is~~ a ~~factor~~ that he is ~~completely addicted to.~~<br><br>~~my web blog~~ ... ~~phone [http:~~//~~www~~.~~january-yjm.com~~/xe/~~index~~.~~php?mid~~=~~video&document_srl~~=~~158289 love psychic~~] ~~readings -~~ [~~http://www~~.~~herandkingscounty~~.~~com/content/information~~-~~and~~-~~facts~~-~~you~~-~~must~~-~~know~~-~~about~~-~~hobbies http://www~~.~~herandkingscounty~~.~~com/content/information~~-~~and~~-~~facts~~-~~you~~-~~must~~-~~know~~-~~about~~-~~hobbies~~],		[[Image:threshold graph.png\|thumb\|240px\|An example of a threshold graph.]]
			In [[graph theory]], a '''threshold graph''' is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:
			#Addition of a single isolated vertex to the graph.
			#Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

			For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.

			Threshold graphs were first introduced by {{harvtxt\|Chvátal\|Hammer\|1977}}. A chapter on threshold graphs appears in {{harvtxt\|Golumbic\|1980}}, and the book {{harvtxt\|Mahadev\|Peled\|1995}} is devoted to them.

			== Alternative definitions ==

			An equivalent definition is the following: a graph is a threshold graph if there are a real number <math>S</math> and for each vertex <math>v</math> a real vertex weight <math>w(v)</math> such that for any two vertices <math>v,u</math>, <math>uv</math> is an edge if and only if <math>w(u)+w(v)\ge S</math>.
			<!-- To see why the two definition are equivalent, observe that a graph constructed using the first definition is also a graph of the second definition by setting <math>S=1</math>, <math>w(u)=1</math> for vertices that were added as dominating vertices and <math>w(u)=0</math> for all other vertices. For the other direction, given <math>S</math> and <math>w</math> we can construct the same graph by starting with the graph whose only vertex is the vertex with the minimum weight and then examining all remaining vertices in order of non-decreasing weight. Each one is added as a -->

			Another equivalent definition is this: a graph is a threshold graph if there are a real number <math>T</math> and for each vertex <math>v</math> a real vertex weight <math>a(v)</math> such that for any vertex set <math>X\subseteq V</math>, <math>X</math> is independent if and only if <math>\sum_{v \in X} a(v) \ge T.</math>

			The name "threshold graph" comes from these definitions: ''S'' is the "threshold" for the property of being an edge, or equivalently ''T'' is the threshold for being independent.

			==Decomposition==
			From the definition which uses repeated addition of vertices, one can derive an alternative way of uniquely describing a threshold graph, by means of a string of symbols. <math>\epsilon</math> is always the first character of the string, and represents the first vertex of the graph. Every subsequent character is either <math>u</math>, which denotes the addition of an isolated vertex (or ''union'' vertex), or <math>j</math>, which denotes the addition of a dominating vertex (or ''join'' vertex). For example, the string <math>\epsilon u u j</math> represents a star graph with three leaves, while <math>\epsilon u j</math> represents a path on three vertices. The graph of the figure can be represented as <math>\epsilon uuujuuj </math>

			==Related classes of graphs==
			Threshold graphs are a special case of [[cograph]]s, [[split graph]]s, and [[trivially perfect graph]]s. Every graph that is both a cograph and a split graph is a threshold graph. Every graph that is both a trivially perfect graph and the [[Complement graph\|complementary graph]] of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of [[interval graph]]s.

			==See also==
			*[[Series-parallel graph]]

			==References==
			*{{citation
			\| last1 = Chvátal \| first1 = Václav \| author1-link = Václav Chvátal
			\| last2 = Hammer \| first2 = Peter L. \| author2-link = Peter Hammer
			\| contribution = Aggregation of inequalities in integer programming
			\| editor1-last = Hammer \| editor1-first = P. L.
			\| editor2-last = Johnson \| editor2-first = E. L.
			\| editor3-last = Korte \| editor3-first = B. H.
			\| editor4-last = Nemhauser \| editor4-first = G. L.
			\| location = Amsterdam
			\| pages = 145–162
			\| publisher = North-Holland
			\| series = Annals of Discrete Mathematics
			\| title = Studies in Integer Programming (Proc. Worksh. Bonn 1975)
			\| volume = 1
			\| year = 1977}}.
			*{{citation
			\| last = Golumbic \| first = Martin Charles \| author-link = Martin Charles Golumbic
			\| location = New York
			\| publisher = Academic Press
			\| title = Algorithmic Graph Theory and Perfect Graphs
			\| year = 1980}}. 2nd edition, Annals of Discrete Mathematics, '''57''', Elsevier, 2004.
			*{{citation
			\| last1 = Mahadev \| first1 = N. V. R.
			\| last2 = Peled \| first2 = Uri N.
			\| publisher = Elsevier
			\| title = Threshold Graphs and Related Topics
			\| year = 1995}}.

			==External links==
			*[http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_328.html Threshold graphs], Information System on Graph Class Inclusions, Univ. of Rostock.

			{{DEFAULTSORT:Threshold Graph}}
			[[Category:Graph families]]
			[[Category:Perfect graphs]]

en>ZéroBot: r2.7.1) (Robot: Adding es:Producto de grafos

2012-07-29T21:47:15Z

r2.7.1) (Robot: Adding es:Producto de grafos

New page

The writer's title is Andera and she believes it sounds fairly great. For a while I've been in Alaska but [http://www.onbizin.co.kr/xe/?document_srl=320614 online psychic chat] I will have to move in a yr or two. Office supervising is what she does for a residing. Playing badminton is a factor that he is completely addicted to.<br><br>my web blog ... phone [http://www.january-yjm.com/xe/index.php?mid=video&document_srl=158289 love psychic] readings - [http://www.herandkingscounty.com/content/information-and-facts-you-must-know-about-hobbies http://www.herandkingscounty.com/content/information-and-facts-you-must-know-about-hobbies],