Peer-Reviewed Publications

      Frustration and isoperimetric inequalities for signed graphs

      Martin, F.
      Published
      Nov 9, 2016
      DOI
      10.1016/j.dam.2016.09.015
      Link to publication
      Summary

      Let Gσ = (V , E , σ ) be a connected signed graph. Using the equivalence between signed graphs and 2-lifts of graphs, we show that the frustration index of Gσ is bounded from below and above by expressions involving another graph invariant, the smallest eigenvalue of the (signed) Laplacian of Gσ . From the proof, stricter bounds are derived. Additionally, we show that the frustration index is the solution to a l1-norm optimization problem over the 2-lift of the signed graph. This leads to a practical implementation to compute the frustration index. Also, leveraging the 2-lifts representation of signed graphs, a straightforward proof of Harary’s theorem on balanced graphs is derived. Finally, real world examples are considered.

      PMIScience.com is operated by Philip Morris International for the purpose of publishing and disseminating scientific information about Philip Morris International’s efforts in support of its smoke-free product portfolio. This site is a global site for use by scientists, the public health and regulatory communities, and other stakeholders with an interest in tobacco policy. The purpose of this site is not advertising or marketing, nor is it directed at any specific market. It is not intended for use by consumers. New tobacco products sold in the United States are subject to FDA regulation; therefore the content of this site is not intended to make, and nor should it be construed as making, any product related claims in the United States without proper FDA authorization. ​
      ​
      Reduced Risk Products ("RRPs”) is the term we use to refer to products that present, are likely to present, or have the potential to present less risk of harm to smokers who switch to these products versus continuing smoking. PMI has a range of RRPs in various stages of development, scientific assessment and commercialization. All of our RRPs are smoke-free products that deliver nicotine with far lower quantities of harmful and potentially harmful constituents than found in cigarette smoke.