Vertex Definition and 136 Threads

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. E

    I Infrared Divergences in Vertex and Self Energy diagrams

    and Link Removed
  2. Anand Sivaram

    I Finding vertex of a 3D Triangle on a Plane

    I came across the following problem and wondering how to solve it. There is a plane n1x + n2y + n3z + n4 = 0 where n1, n2, n3, n4 are known. The triangle is in this plane. We already know the two vertices P1(x1, y1, z1), P2(x2, y2, z2) of the triangle. Now we have to find the third vertex P(x...
  3. theittsco

    A Renormalization with hard cutoff of a loop diagram with single vertex

    Trying to solve for the loop contribution when renormalizing a one loop ##\frac{\lambda}{4!}\phi^4## diagram with two external lines in ##d=4## dimensions. After writing down the Feynman rule I see that: $$\frac{(-i\lambda)}{2}\int d^4q \frac{i}{q^2-m_{\phi}^2+i\epsilon} $$ But I see no way to...
  4. E

    A The vertex factors in QCD penguin operators

    Have a look at O5 & O6 in Eqtns(5.4) . Why is there a (V+A) ? (V+A) contains the projection operator which projects out the right Weyl from a Dirac spinor. As per the Feynman rules of electroweak theory, there is a (V-A) assigned to each (Dirac) spinor-W boson vertex because W only couple to...
  5. simplemind

    I Are Different Charged Gluons Repulsive in the Gluon-Gluon Four-Point Vertex?

    Hello, First,i am an absolute beginner in QCD. As i have seen there are six different Feynmangraphs for the Four-Point vertex. Swordfish,Box,... I am interested in the first of the six where the two gluons met in a point and goes away. My question now is. If for this case two different...
  6. dontknow

    I Causality for internel vertex in Feynaman diagrams

    Eq 4.44 in Peskin and Schroeder. My question is: Does causality imply that time coordinates of z (internal vertex over which we doing the integration) should lie between the time coordinates of field phi(x) and phi(y)?
  7. archaic

    Cube with charges at each vertex

    For convenience, I take the center of the upper face. The charges at the top cancel each other's effects, and those at the bottom cancel each other's horizontal effects, so I get$$E=4k\frac{q}{r^2}\sin\theta$$I have found that ##\theta=\arcsin\left(\frac{s}{r}\right)=\arcsin{\sqrt\frac{2}{3}}##...
  8. saadhusayn

    A Two loop Feynman diagram with quartic vertex

    I am trying to calculate the effective potential of two D0 branes scattering in Matrix theory and verify the coefficients in this paper: K. Becker and M. Becker, "A two-loop test of M(atrix) theory", Nucl. Phys. B 506 (1997) 48-60, arXiv:hep-th/9705091. The fields are expanded about a constant...
  9. C

    I No "i" in the Triple gluon vertex Feynman Rule

    This is probably a simple question but puzzled me a little when trying to explain something to somebody. In all resources online and in most books I've seen, the triple gluon vertex has no overall 'i' factor while e.g. the four gluon vertex always does. The photon and gluon propagators as well...
  10. F

    Parabola: Vertex =(?,0) and know 2 arbitrary points. How solve x?

    Summary:: I have a upwards opening parabola where I know the Y vertex point = 0. I also know 2 arbitrary points separated by a step size on the parabola. How can I solve for x at the vertex point? X=horizontal plane Y=vertical plane I have a upwards opening parabola where I know the Y vertex...
  11. The black vegetable

    I Vertex function, quantum action

    I am looking at Srednicki ch 64 , how does equation 64.1 follow from 64.3 as stated. Explicitly in QED how does ## u_{s'}(p')V^{u}(p',p)u_{s}(p)=e\bar{u'}(F_{1}(q^{2})\gamma ^{u}-\frac{i}{m}F_{2}(q^{2})S^{uv}q_{v})u ## follow from the quantum action ## \Gamma =\int d^{4}x(eF_{1}\bar{\varphi...
  12. takunitoche

    A Derivation of the Yang-Mills 3 gauge boson vertex

    Hello everyone, I am stuck in the derivation of the three gauge-boson-vertex in Yang-Mills theories. The relevant interaction term in the Lagrangian is$$\mathcal{L}_{YM} \supset g \,f^{ijk}A_{\mu}{}^{(j)} A_{\nu}{}^{(k)} \partial^{\mu} A^{\nu}{}^{(i)} $$ I have rewritten this term using...
  13. takunitoche

    Three gauge boson Yang-Mills vertex

    Hello everyone, I am stuck in deriving the three gauge-boson-vertex in Yang-Mills theories. The relevant interaction term in the Lagrangian is $$\mathcal{L}_{YM} \supset g \,f^{ijk}A_{\mu}{}^{(j)} A_{\nu}{}^{(k)} \partial^{\mu} A^{\nu}{}^{(i)} $$ I have rewritten this term using the...
  14. S

    MHB Find vertex, focus, and directrix of parabola: y^2+12y+16x+68=0

    Find the vertex, focus, and directrix of the following parabola: y^2+12y+16x+68=0 The form we have been using is (y-k)^2=4p(x-h) Any explanation would help too, I'm really stuck on this one. Thank you!
  15. Jamister

    A Electron Vertex Function in QED

    In Peskin book they calculate the QED Vertex Function named Gamma which depend on two scalar functions called form factors F1(q^2), F2(q^2). they are calculating F1(q^2) and they do not really finish calculating for what I understand. They are just showing the Infrared divergent is canceled by...
  16. Wrichik Basu

    I Some questions in QFT (EM vertex, Ward identity, etc.)

    I am reading the A First Book of Quantum Field Theory. I have reached the chapter of renormalization, where the authors describe how the infinities of the self-energy diagrams can be corrected. They have also discussed later how the infrared and ultraviolet divergences are corrected. Just before...
  17. Wrichik Basu

    B General form of electromagnetic vertex function in QFT

    I am studying a beginner's book on QFT. In a chapter on electromagnetic form factors, the authors have written, using normalized states, $$\begin{eqnarray} \langle \vec{p'}, s'| j_\mu (x) |\vec{p}, s \rangle \ = \ \exp(-i \ q \cdot x) \langle \vec{p'}, s'| j_\mu (0) |\vec{p}, s \rangle...
  18. Wrichik Basu

    I One vertex interactions in QED - error in the book?

    I am studying QFT from the book A First Book of QFT. I am currently in the chapter of QED. The authors have written down the interaction Lagrangian for QED. Thereafter, they have taken a special case of the electron, and written down the normal-ordered interaction Hamiltonian for this case...
  19. S

    I Finding the dependence of maximum vertex degree on k-colorability

    How do we describe a construction of a 2-colorable graph where the degree of every vertex is greater than or equal to (|V|-1)/2? Based on that, what can be said about the dependence of maximum vertex-degree on k-colorability of a graph? My first thought is that in order for a vertex to connect...
  20. M

    MHB The shifting of h in vertex form

    The Role of H in the quadratic function ( vertex form) i get that this is how its written on a graph y=(x-2)^2+k that the graph looks as if the value of h is positive as in +2 ( however its value is actually negative) looks like it shifted right my textbook contradicts itself y=3(x-1)^2 +2...
  21. M

    Feynman's rule for Photon/W+/W- vertex

    Homework Statement Hello there! I've been trying to obtain the Feynman rule (tree level) for a photon/W+/W- vertex in SM, but I don't really know hoy to get it. I've been told that there's a trick to obtain these rules, which consists in changing partials for momentums: \partial_\mu...
  22. Krushnaraj Pandya

    Electric field and potential at vertex of cube

    Homework Statement A solid non-conducting cube of side l and uniformly distributed charge q, has electric field E and potential V at one of its vertex, imagine this cube to be made of 8 smaller cubes of side l/2. if one such cube is removed, find the new field and potential at the point where...
  23. binbagsss

    Feynman Vertex Rule, Correlator, 2 different coupling constants

    Homework Statement Vertex Feynamnn rule for computing the time correlator of fields under an action such as, for example, Say ##S_{int} [\phi] =\int d^4 x \lambda \frac{\phi^4(x)}{4!} + g \frac{\phi^4(x)}{4!} ##, ##\lambda## and ##g## the coupling constants. Homework Equations see below...
  24. P

    I Feynman Diagram-Momentum conservation in primitive vertex

    In the first Feynman diagram, an electron comes in, emits a photon and then leaves. Is this an allowed process? Because if you rotate the diagram by 90o, the diagram should be just as valid, but it doesn't seem to be since it would violate the law of conservation of momentum. So is the...
  25. karush

    MHB 231.13.3.75 top vertex of a regular tetrahedron

    $\tiny{231.13.3.75}$ $\textrm{Imagine $3$ unit spheres (radius equal to 1) with centers at,}\\$ $\textrm{$O(0,0,0)$, $P(\sqrt{3},-1,0)$ and $Q(\sqrt{3},1,0)$.} \\$ $\textrm{Now place another unit sphere symmetrically on top of these spheres with its center at R.} \\$ $\textrm{a Find the...
  26. parshyaa

    Find the third coordinate of a vertex of an equilateral triangle

    Homework Statement Q. Prove that If (x1,y1) and (x2,y2) are the coordinates of the two vertices of an Equilateral Triangle then the coordinates of the 3rd vertex (X,Y) are $$X=\frac{x1+x2\pm\ √3(y1-y2)}{2},$$ $$Y=\frac{y1+y2\pm\ √3(x1-x2)}{2},$$ The Attempt at a Solution I used distance...
  27. oohaithere

    Moment of Inertia of equilateral triangle about vertex

    Homework Statement A piece of thin uniform wire of mass m and length 3b is bent into an equilateral triangle. Find the moment of inertia of the wire triangle about an axis perpendicular to the plane of the triangle and passing through one of its vertices. Homework Equations Slender rod, axis...
  28. Andrea_G

    A Four Bosons vertex related to gauge symmetry

    Hi, is correct to say that there is no interaction between four photons because the gauge group of QED is U (1) while there are interactions of four gluons or four W's because the gauge group of QCD is SU (3) and EW's one is SU (2) xU (1)? I know that the interaction between four photons is not...
  29. M

    MHB From quadratic form to vertex form

    $-x^2+4x-1$ should be converted to the vertex form of $y=k-(x-h)^2$ How can this be solved by factoring or any other method ? My attempt to solve this problem , I will be using the completing the square method, $\left(-x^2+4x+\frac{-b}{2a}\right)=1+\frac{-b}{2a}$ Here $\frac{-4}{-2}=2$...
  30. math4everyone

    Electric potential at the vertex of a triangle

    I am stuck with this problem: The right triangle shown with vertex P at the origin has base b, altitude a, and uniform density of surface charge σ. Determine the potential at the vertex P. First find the contribution of the vertical strip of width dx at x. Show that the potential at P can be...
  31. steele1

    Prove area of triangle is given by cross products of the vertex vectors....

    Homework Statement The three vectors A, B, and C point from the origin O to the three corners of a triangle. Show that the area of the triangle is given by 1/2|(BxC)+(CxA)+(AxB)|. Homework EquationsThe Attempt at a Solution I know that the magnitude of the cross product of any two vectors...
  32. M

    MHB Construct vertex D of an acute angled triangle

    For a closer look click here Any Ideas on how to begin? Many Thanks :)
  33. ShayanJ

    A Vertex, Propagator and Loop counting

    I'm reading these lecture notes but there is something I don't understand. In page 15, it starts to consider vacuum diagrams of various orders and tries to associated a factor to them according to the rule: ## diagram \sim (\frac \lambda N)^p(\frac N \lambda)^v N^l=\lambda^{p-v} N^{l+v-p}##...
  34. Evangeline101

    Function: expressing functions in vertex form.

    Homework Statement 2. Homework Equations The Attempt at a Solution a) [/B]f(x) = -5x2 + 20x + 2 y = -5x2 + 20x + 2 Factor -5 from the first two terms: y = -5x2 + 20x + 2 = -5 (x2 – 4x) +2 Complete the square in the bracket: (1/2 b)2 = [1/2 (-4)]2 = (-2)2 = 4 Group the perfect...
  35. M

    How to find Lagrangian density from a vertex factor

    Homework Statement This isn't a homework problem, per se, in that it's not part of a specific class. That being said, the question I would like help with is finding a Lagrangian density from the vertex factor, $$-ig_a\gamma^{\mu}\gamma^5.$$ This vertex would be identical to the QED vertex...
  36. A

    I can really use a hand on finding vertex

    Homework Statement find the slandered equation of a parabola that has a vertex axis that satisfies the given condition. X intercepts -3 and 5 Y coordinate 4 Homework Equations A(x-h)^2+k=yThe Attempt at a Solution -4(x-1)^2+4
  37. Julian102

    If two vertices of a square on the same side AB are A(1,2) and B(2,4)....

    Homework Statement If two vertex of a square of the side AB is A(1,2) and B(2,4) find other two vertex C and D? Homework Equations 1. y-y1 = m ( x-x1) 2. m=y1-y2 / x1-x2 3. m1*m2= -1 4. (x-x1) / (x1-x2) =(y-y1)/(y1-y2) 5. m=tanA 6. If ax+by+c=0 then its parallel line is ax+by+k=0 The Attempt...
  38. S

    Vertex of Parabola: Find y^2-12=12x Solution

    Homework Statement I'm trying to find the vertex of this parabola: y^2-12=12x The Attempt at a Solution Initially I tried to take the derivative and find the vertex by finding where it the function is zero, but apparently that does not work in this situation. Is it because it is not in...
  39. M

    Help me to understand the QCD vertex factor

    Guys...help me out to understand this 3-vertex factor of non-abelian and or QCD fields. it is from peskin & schroeder page 507.
  40. C

    Intersection of two parabolas where one is vertex shifted

    Not a homework question but this seems to be the appropriate place... 1. Homework Statement I would like to be able to calculate the intersections of two parabola's which accounts for one or both of the parabola's being shifted along the x axis I have written an excel vba function to do this...
  41. C

    Path of an object at the vertex of an equilateral triangle

    Homework Statement There are three objects at the Vertices of an equilateral triangle that start movin towards each other at the same time with a speed v. Describe the path of the objects and the time taken for them to meet. Homework Equations V1=v3 - v2 Where all velocities are in...
  42. T

    How do I graph in vertex form with an equation like (x+1/2)^2 = 12(y - 3)?

    I've run into stumbling block here, is some sort of conversion required when your equation looks like: (x+1/2)^2 = 12(y - 3). Do I move it to standard form or can I graph it as is?
  43. C

    MHB Finding a Quadratic Function from a Vertex

    Hello, I'm having some trouble on this question, and I'd imagine it's just because I'm looking at it incorrectly. The problem statement is: The quadratic function f(x) = p + qx - x2 has a maximum value of 5 when x = 3 (i.e. vertex at (3, 5), right?) Find the value of p and the value of q...
  44. D

    Momentum conservation at vertex in Feynman Diagrams

    Hey guys, I need help with conserving momentum at these vertices (this is Bhabha scattering): So in Diagram (a), the first vertext to the left. The incoming momenta are p_{1}+p_{2}. The outgoing momentum I'll call it p. So...shouldnt I have p_{1}+p_{2}=p? Furthermore, is the propagator...
  45. N

    How to find the vertex of G(t)=1/2(t^2-4t)

    Homework Statement G(t)=1/2(t^2-4t) The Attempt at a Solution Since this is a polynomial it's all real numbers for domain y-int: G(0)=1/2(0^2-4(0) y-int=(0,0) x-int: 0=1/2(t^2-4t) 0=(1/2)t(t-4) Not sure... And not sure about the vertex. I know the formula -b/2a but how do i find those two...
  46. N

    Standard form, vertex form. Something isn't right here

    I mainly just need some clarification here. I was doing my homework and then browsing the web to find an answer to my problem and came across mathewarehouse' definition of Standard form and then I looked at my homework and went..."huh?" I don't understand if my homework is listening this wrong...
  47. S

    MHB Find the equation of parabola with vertex (2, 1) and focus (1, -1)

    Hello friends. This is my first post. I am given the following problem: Find the equation of parabola with vertex (2, 1) and focus (1, -1) I have tried to solve this question in this way: Since vertex is mid point of Focus and the point which touches the Directrix. From this, I calculate that...
  48. E

    Advice for gluon vertex textbook

    Hello everyone, i'm having a hard time trying to derive the three gluon vertex in QCD, using the generating functional. Could someone please suggest a reference where it is computed step by step? My teacher lecture notes are not clear, and basically I don't understand what he's doing. A very...
  49. G

    Understanding 1PI Vertex and Self-Energy Conventions in Quantum Field Theory

    I assume that if your theory has an interaction term written as LI= ±λ*fields, where λ is the coupling, that the 1PI vertex is defined as: $$i(\pm \Gamma)=i(\pm \lambda)+loops$$ That way to tree level, Γ is λ, and not -λ. The exception seems to be the self-energy. A mass term has -m2*field2...
  50. WannabeNewton

    Vertex corrections 1-loop order Yukawa theory

    Consider the Yukawa theory ##\mathcal{L}_0 = \bar{\psi}_0(i\not \partial - m_0 - g\phi_0)\psi_0 + \frac{1}{2}(\partial \phi_0)^2 - \frac{1}{2}M_0^2 \phi_0^2 - \frac{1}{4!}\lambda_0 \phi_0^4## with cutoff ##\Lambda_0##; a lower cutoff ##\Lambda < \Lambda_0## is then introduced with an effective...
Back
Top