Results 1 to 10 of about 38,756 (312)
Journal of Combinatorial Theory, Series B, 2018 Let $G=(V,E)$ be a graph and let $A_G$ be the clique-vertex incidence matrix of $G$. It is well known that $G$ is perfect iff the system $A_{_G}\mathbf x\le \mathbf 1$, $\mathbf x\ge\mathbf0$ is totally dual integral (TDI). In 1982, Cameron and Edmonds proposed to call $G$ box-perfect if the system $A_{_G}\mathbf x\le \mathbf 1$, $\mathbf x\ge\mathbf0$
Zang, W, ZHAO, Q, Ding, G
openaire +5 more sources
INDUCED REGULAR PERFECT GRAPHS
South East Asian J. of Mathematics and Mathematical Sciences, 2023 A graph G is said to be R-perfect if, for all induced subgraphs H of G, the induced regular independence number of each induced subgraph H is equal to its corresponding induced regular cover. Here, the induced regular independence number is the maximum number of vertices in H such that no two belong to the same induced regular subgraph in H, and the ...
Jayakumar, Gokul S., V., Sangeetha
openaire +2 more sources
Square-free perfect graphs [PDF]
Journal of Combinatorial Theory, Series B, 2004 We prove that square-free perfect graphs are bipartite graphs or line graphs of bipartite graphs or have a 2-join or a star cutset.
CONFORTI, MICHELANGELO +2 more
openaire +2 more sources
Exploration of CPCD number for power graph
مجلة بغداد للعلوم, 2023 Recently, complementary perfect corona domination in graphs was introduced. A dominating set S of a graph G is said to be a complementary perfect corona dominating set (CPCD – set) if each vertex in is either a pendent vertex or a support vertex and ...
S. Anuthiya, G. Mahadevan, C. Sivagnanam
doaj +1 more source
Planar cycle-extendable graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceFor most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs - that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching.
Aditya Y Dalwadi +3 more
doaj +1 more source
All Pairs of Pentagons in Leapfrog Fullerenes Are Nice
Mathematics, 2020 A subgraph H of a graph G with perfect matching is nice if G−V(H) has perfect matching. It is well-known that all fullerene graphs have perfect matchings and that all fullerene graphs contain some small connected graphs as nice subgraphs.
Tomislav Došlić
doaj +1 more source
Balancedness of subclasses of circular-arc graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2014 Graph ...
Flavia Bonomo +3 more
doaj +1 more source
Random Structures & Algorithms, 2018 We investigate the asymptotic structure of a random perfect graph Pn sampled uniformly from the set of perfect graphs on vertex set . Our approach is based on the result of Prömel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly.
McDiarmid, C, Yolov, N
openaire +2 more sources
Characterizing ‐perfect line graphs [PDF]
International Transactions in Operational Research, 2016 AbstractThe aim of this paper is to study the Lovász‐Schrijver PSD operator applied to the edge relaxation of the stable set polytope of a graph. We are particularly interested in the problem of characterizing graphs for which generates the stable set polytope in one step, called ‐perfect graphs.
Escalante, Mariana Silvina +2 more
openaire +5 more sources
Line game-perfect graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceThe $[X,Y]$-edge colouring game is played with a set of $k$ colours on a graph $G$ with initially uncoloured edges by two players, Alice (A) and Bob (B). The players move alternately. Player $X\in\{A,B\}$ has the first move. $Y\in\{A,B,-\}$.
Stephan Dominique Andres, Wai Lam Fong
doaj +1 more source