What is Vertex: Definition and 136 Discussions

In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.
The minimum vertex cover problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem.
Vertex cover problems have been generalized to hypergraphs, see Vertex cover in hypergraphs.

View More On Wikipedia.org
Recent contents Top users
  1. maverick280857

    Conformal weights of the vertex operator

    Hi, I'm trying to prove that the conformal weight of the bosonic vertex operator :e^{ik\cdot X}: is \left(\frac{\alpha'k^2}{4},\frac{\alpha'k^2}{4}\right). I've done some algebra but I think I am making some mistake with a factor of 2 somewhere because I get a 1/2 instead of a 1/4. My attempt...
  2. J

    MHB NP Problems: Weighted Vertex Cover vs Weighted Independent Set

    There is a Theorem that states that if G = (V, E) is a graph, then S is an independent set $\Leftarrow\Rightarrow$ V - S is a vertex cover. Suppose the vertices have positive integer weights. Does it follow from the theorem that: S is an independent set with maximum weight...
  3. Safinaz

    What is wrong with my implementation of Yukawa Lagrangian using Feynrules?

    Hi all, I wonder if anyone here is familiar with Feynrules package to implement new model by Mathematica. Actually I'm a new user for and try to implement Yukawa Lagrangian for new charged Higgs scalar called X and the charge conjugate Xbar with the SM fermions, I wrote the Lag. as : LX := X...
  4. A

    MHB How to Determine the Vertex of a Parabola?

    The general equation of the parabola has the form $Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$ with $B^2 = 4AC$ what is the coordinate of the vertex of the parabola or in other word how to determine the vertex of a given parabola for example $4x^2 + 4xy + y^2 - 5x + 7y + 11 =0 $ Thanks.
  5. Joffan

    Sum of arbitrary vertex to midpoint vectors

    I was looking at a homework question posted here requiring proof that the vectors from the vertices of a triangle to the midpoint of the opposite edge sum to zero, and it struck me that there is a more general property: Consider a set of points, \{A_0, A_1, \ldots A_n\}. The midpoint of...
  6. P

    Define Tetrahedron knowing one vertex, 3 vectors, opposite face.

    I have a unique problem that I'm struggling with with regards to surveying. Because my surveying equipment is much more accurate at measuring angles than distances I'd like to find an analytic solution using only the angular measurements. Let the surveyor sit at the origin of the...
  7. H

    Vertex Function & Wave Function of Mesons: Exploring Their Relation

    I need to know the relation of wave function and vertex function of mesons. Any one give me an explanation of them. Are they same? in some journals their expressions are the same and in other papers the wave function expresses as a function of the vertex function of meson. Which one is the...
  8. T

    4th Vertex in a 3D Parallelogram

    Homework Statement Let P, Q, and R be the vertices of a parallelogram with adjacent sides PQ and PR. Find the other vector S. P (2, 0 ,-1), Q (-2, 4, 1), R (3, -1, 0) Homework Equations PR = QS PQ = RS The Attempt at a Solution I took the two equations and solved both of them...
  9. Drakkith

    Vertex of a Function: -3(x-2)^2-3

    I have the following function and I'm supposed to find the vertex of its graph. f(x)=-3(x-2)2-3 Why is the vertex (2,-3) instead of (-2,-3)? Edit: Bah, nevermind. I just realized the formula has (x-h) in it, not (x+h) in it...
  10. D

    MHB Finding the vertex of a quadratic and the product of two complex numbers

    Basically I don't know anyone in real life that can help me with this, so I need help checking to see if my answers are correct :) PART A 11) Find the vertex of f(x) = -2x^2 - 8x + 3 algebraically. My Answer: (-2,0) 12) Multiply and simplify: (6 - 5i) (4 + 3i) My Answer: 39 - 2i
  11. G

    Relationship between vertex function and current

    Is there a proof or obvious reason why the vertex function is related to the current via: S(p')\Gamma^\mu(p',p)S(p)=-\int \int dxdy e^{ipx}e^{-ipy} \langle T \psi(x) j^\mu(0) \bar{\psi}(y)\rangle In the free-field case one can see it's true. But the interacting case?
  12. A

    MHB Prove Triangle-Free Graph w/ 2n/5 Degree is Bipartite

    In a group of n people, each pair are friends or strangers. No set of three people are mutually friends. For any partition of the n people into two groups, there exists two people in a group that are friends. Prove that there exists a person who is friends with at most 2n/5 people in the group...
  13. N

    (Peskin and Schroeder) Numerator of vertex correction

    Hi I am studying qft with worldwidely used text, written by Peskin and Schroeder, An introduction to qft. I have trouble with the calculation of thr numerator on pp. 192. I got additional term ## 2m(z-xy)(mγ^μ - p^μ) ## between spinors, which seems not vanishing. Is there any idea to treat this...
  14. C

    RG equation and invariance of the vertex function under scaling(Ryder)

    Hi. I have trouble understanding an argument in Lewis H. Ryder's QFT (second edition) at page 325 where he wants to write down an equation similar to the renormalization group equation which expresses the invariance of the vertex function \Gamma^{(n)} under the change of scale. The relevant...
  15. M

    Vertex factor for W^- -> e + anti neutrino_e

    Hi, I'm wondering if anyone can give me some advice on working out the vertex factor from a lagrangian. I think I know what I should be doing however it isn't quite getting the right answer so if anyone could guide me that would be great. \mathcal{L}_{W^-e^-\nu_e} =...
  16. Saitama

    How Does Force Applied to One Vertex Affect Opposite Vertex in a Square Frame?

    Homework Statement Four similar rods of uniform density are connected with frictionless hinges, and this frame is placed to a horizontal smooth tabletop, such that its shape is a square. Vertex P is acted upon by a horizontal force in the direction of the diagonal, and due to this force it...
  17. G

    Renormalized vertex always a log?

    Is there a reason that one-loop corrections to vertex functions seem to always be logarithmic? If you write the vertex as a Taylor series in the external momenta, then the first couple of terms (say the constant and linear terms) diverge, but these divergence gets subtracted off, so you now...
  18. C

    Vertex form of parabola; why x-h, not x+h?

    Hello. The vertex form is y= a(x-h)^2+k, in general. Could it also be defined as y= a(x+h)^2+k? I am wondering about that minus sign. I see no particular use of it. Is it there because of tradition or am i missing something?
  19. S

    Photon-Massive Vector Boson Vertex Feynman Rule

    1. The Problem I am trying to find the feynman rule which corresponds to the addition of an interaction term to the QED lagrangian which couples the electromagnetic field to a neutral massive vector boson field. In this problem, $$k^\mu$$ corresponds to the photon 4-momentum and $$q^\mu$$...
  20. E

    Vertex Feynman Rule Derivations

    Alright, this is a pretty low level / silly question but I am having some issues. I would like to get the vertex rule for an interaction that has a field tensor involved like this... \partial_\mu Z_\nu -\partial_\nu Z_\mu do I treat the two Z's as separate fields? For a generic field...
  21. Hepth

    Chiral Perturbation Theory : pi0 pi0 Z vertex?

    Not sure if anyone has any experience with chiral perturbation theory, but I'm trying to see what all of the vertices are for interactions with a single Z boson. I've looked at the lagrangian up to order p^4 so far, and it seems that the Z only interacts with charged pions/kaons. I'm using...
  22. R

    Neighboring triangles of each vertex

    I have a mesh with unstructured triangular grid. I need to find neighboring triangles of each vertex. How can I do it? Thanks before :D
  23. B

    Construct quadratic equation using the vertex method

    Homework Statement Folks, I wish to construct a quadratic expression from a graph which has the following 2 coordinates. ##(0,0)## and the vertex ##(\alpha h_e,1)## where ##0<\alpha<1## Homework Equations Using the following ##y(x)=a(x-h)^2+k## The Attempt at a Solution...
  24. C

    Collider Parameters: corrected time for wrong vertex

    Hello, I stumbled across the following equation in a presentation about collider physics: tcorrWV =(tiRV - tiWV) + (TOFRV - TOFWV), where tcorrWV is the corrected time for the wrong vertex, tiRV is the initial time of the right vertex, tiRV is the initial time of the wrong vertex...
  25. L

    What is the Nolting spin product of graphs?

    Look at the page 256. relation (6.93). http://books.google.rs/books?id=vrcHC9XoHbsC&pg=PA256&lpg=PA256&dq=Nolting+spin+product+of+graphs&source=bl&ots=5uRIg5aDIj&sig=sawJYioGHevsuCjxs-NNv_OxSrY&hl=sr#v=onepage&q=Nolting%20spin%20product%20of%20graphs&f=false What is even vertex? Can you...
  26. bcrowell

    Why exactly three lines at a Feynman vertex?

    The Feynman diagram you'd naively draw for a beta decay such as p\rightarrow n + e^++\bar{\nu} would have four lines joined at a vertex, but in reality there's a virtual W or Z involved, which makes it into two 3-vertices. Is there any fundamental reason why all the vertices in a field theory...
  27. A

    Solving a 'skew' quadrilateral for vertex position.

    I've been scratching my head over this one. I'm trying to find a system of equations to solve for points R and S. The known parameters are: Point Q, tangent vector t and the axis vector a. The following vectors are perpendicular to each other: a,d a,b b,c c,t d,t The other known...
  28. M

    How to calculate the fourth vertex of a parallelogram

    given 3 vectors : a=(1,3,4) b=(2,5,3) c=(1,0,0)
  29. I

    Conformal Field Theory: Evaluating the Vertex Operator on the Vacuum

    Homework Statement Evaluate \lim_{z \to 0}:e^{ik \cdot X(z)}:|0\rangle where X(z) is a free chiral scalar field in the complex plane. Homework Equations In Conformal Field Theory, the free chiral scalar field in the complex plane is given by: \begin{array}{rcl} X(z) &=& \frac{1}{2}q -...
  30. M

    MHB Finding the vertex, y-intercept and axis of symmetry

    I am lost and confused. I have been on the same problem for 2 hours. I know all the formulas, but I'm not doing something right...
  31. H

    MHB Finding the equation of vertex of right angle triangle

    Points (6,0) and (O,8) are the endpoints of the hypotenuse of a right-angled triangle, whose other vertex is at (x,y). What equation relates x and y?Attempt at solution: So What I am thinking is that the line will be perpendicular to the line with end points 6,0 and 0,8. So The gradient of...
  32. H

    Finding the equation of vertex of right angle triangle

    Points (6,0) and (O,8) are the endpoints of the hypotenuse of a right-angled triangle, whose other vertex is at (x,y). What equation relates x and y?Attempt at solution: So What I am thinking is that the line will be perpendicular to the line with end points 6,0 and 0,8. So The gradient of...
  33. F

    Vertex of Fundamental Domains & Elliptic Points

    Dear Folks: Suppose \Gamma is a discrete subgroup of SL2(R), which acts on the upper half complex plane as Mobius transformation. F is its fundamental domain. If z is a vertex of F which does not lie on the extended real line ( that is R\bigcup\infty ) ,then must x be an elliptic point...
  34. S

    Question on the form of a vertex operator in a proof

    [Closed] Question on the form of a vertex operator in a proof Ok, never mind - I decided to find the solution in a different way.. This is a little too specialized anyway. (Is there a way to delete the thread?) Hi, I am reading paper [1] and I found that formula (33), \psi(xy)\psi^*(y)=\frac...
  35. S

    Finding vertex of quadratic equation?

    I have to find the vertex, axis, domain, & range of this quadratic equation: f(x)= -1/2(x+1)^2 -3 I can't remember how to do the vertex. Is it y= -b/2a? Also, I tried factoring the equation, but I think I messed up. I ended up with: f(x)= .25x^2 +.5x-2.75 Thanks
  36. M

    Finding Coordinates of last Triangle Vertex

    Hi, I am trying to find the last vertex coordinates of a triangle given that Vertex 1 = (2,10) Vertex 2 = (3,6) Angle at Vertex 1 = 75.9638 degrees Angle at Vertex 2 = 70.3462 degrees. I have tried using the equations based on the length of each side, as well as using the cos dot...
  37. tom.stoer

    Constraints, measure and vertex amplitude in LQG

    Have a look at http://arxiv.org/abs/1202.5039 Degenerate Plebanski Sector and its Spin Foam Quantization Authors: Sergei Alexandrov (Submitted on 22 Feb 2012) Abstract: We show that the degenerate sector of Spin(4) Plebanski formulation of four-dimensional gravity is exactly solvable and...
  38. A

    Finding the equation of a parabola with only 2 x-intercepts and the vertex

    1. Write an equation of the quadratic function f whose graph has x-intercepts 3 and 7 and f(5) = 8. 2. I really don't know where to go from here :frown: 3. obviously, is the x-int. are 3 and 7 that means they are points (3,0) and (7,0). Also, f(5) = 8 becomes the point (5,8) which i have found...
  39. A

    Weak force vertex factor V - A

    Hi forum, The weak force vertex factor is γu(1-γ5). Am I right that the axial component only couples to left handed fermions? Does the vector component couple to both left and right-handed fermions? Thanks, Mark
  40. Telemachus

    Three equal charges are situated at the vertex of an equilateral

    Hi there. I did this problem, and I wanted to know if my solution is ok. The problem says: Three equal charges are situated at the vertex of an equilateral triangle, and we want to cancel out the forces exerted by each other. What charge q' of opposite sign should be placed at the center of the...
  41. C

    How to derive a numerator relation in vertex correction in Peskin p191

    i.e. thank you very much in advance
  42. A

    A question about the minimal vertex possible

    hi in "Introduction to Elementary Particles" ed. 2 / David Griffiths the writer states that a bilinear vertex in two different fields is always impossible (my words). or in other words: theoretically we can't have a fundamental vertex with one particle coming in and one going out. and...
  43. T

    Find the equation of a parabola with a given focus and vertex.

    Homework Statement Find the equation of a parabola with a vertex of (1,-3) and focus of (1,-1)? Homework Equations The Attempt at a Solution
  44. H

    Rewriting f(x) as a Transformation of g(x)

    Homework Statement Can someone assist me with number 3 please... Homework Equations The Attempt at a Solution I went ahead and rewrote f(x) in vertex form in terms of a,b, and c but I'm having a hard time writing down how f can be thought of as a transformation of g.
  45. J

    Proof of Four Vertex Theorem for Convex Figure | Do Carmo

    I just began to read Do Carmo's Differential Geometry book and having breezed through most of the chapter 1, I am finding it difficult to see how the four vertex theorem for a convex figure is proved? Could someone please provide a simple and easy to understand proof?
  46. P

    Computing the 1-loop Correction to the 3 Gluon Vertex with Non-Zero Quark Mass

    Anyone know a reference in the literature that computes the correction to the 3 gluon vertex due to a quark loop with non-zero quark-mass?
  47. J

    Find the top vertex coordinate of a regular tetrahedron

    Homework Statement A regular tetrahedron has the vertices of its base A(1,1,0) B(3,1,0) C(2,1+(3^(1/2),0). Find coordinate of vertex S? Homework Equations The Attempt at a Solution If this is a tetrahedron Then we know the length by caclulating the distance formula, which gives...
  48. T

    Conformal field theory: vertex operator

    I am getting apparently conflicting statements about the conformal transformation law of the vertex operator appearing in and 2D QFT (such as in bosonic string theory). For example, according to http://en.wikipedia.org/wiki/Conformal_field_theory" (eqn 64 on page 15), the transformation law is...
  49. T

    QED: Vertex renormalisation; Please have Peskin and Schroeder book handy

    Hi guys, I have a question regarding a point in the QFT book of peskin and schroeder. Iv been working through renormalisation in QED, The 2-point corrections are simple enough, however in this book the 3-point function is a little more involved and I have some issues. Essentially id to...
  50. J

    Finding the Vertex of a Parabola: A Quick Guide

    Homework Statement Find the vertex of the parabola y = (a-b)(a+b) Homework Equations x = -b/2a The Attempt at a Solution This question was extra credit on my Pre-Calc test today. I got the answer and it took almost a page to do it. But I'm very anxious and I just can't wait until i get my...
Back
Top