1,720,966 research outputs found
Edge contraction and cop-win critical graphs
No full textThe problem is to determine the number of ‘cops’ needed to capture a ‘robber’ where the game is played with perfect information, the different sides moving alternately. The cops capture the robber when one of them occupies the same vertex as the robber at any time in the game. A copwin graph is one in which one cop can always capture the robber. A graph is cop-win edge-critical with respect to edge contraction (CECC) when the original graph is not cop-win, but the contraction of any edge results in a cop-win graph. In this paper, classes of CECC graphs are determined, and k-regular CECC are characterized for k ≤ 4
Non 3-choosable bipartite graphs and the Fano plane
No full textIt is known that the smallest complete bipartite graph which is not 3-choosable has 14 vertices. We show that the extremal configuration is unique.PT: J; CR: BROWN E, 2002, MATH MAG, V75, P83 ERDOS P, 1979, CONGRESSUS NUMERANTI, V26, P155 FITZPATRICK SL, DMS854IR U VICT DEP HAUSON D, 1996, ARS COMBINATORIA, V44, P183 VIZING VG, 1976, DISKRET ANAL, V29, P3 WOODALL DR, 2001, LONDON MATH SOC LECT, V288, P269; NR: 6; TC: 0; J9: ARS COMB; PG: 15; GA: 948CQSource type: Electronic(1
- …
