KONECT
KONECT > Statistics > 4-tour count

## 4-tour count

A cycle cannot the same node twice. Due to this combinatorial restriction, $$C_k$$ is quite complex to compute for large $$k$$. Therefore, we may use tours instead, defined as cyclical lists of connected vertices in which we allow several vertices to overlap. The number of $$k$$-tours will be denoted $$T_k$$. For computational conveniance, we will define labeled tours, where two tours are not equal when they are identical up to shifts or inversions. We note the following equalities: \begin{align} T_1 &= 0 \nonumber \\ T_2 &= 2m \nonumber \\ T_3 &= 6t \nonumber \\ T_4 &= 8q + 4s + 2m \end{align} Again, these are true when the graph is loopless. The last equality shows that trying to divide the tour count by $$2k$$ to count them up to shifts and inversions is a bad idea, since it cannot be implemented by dividing the present definition by $$2k$$.

 Code Name Category F. W. M. $$n$$ $$m$$ $$T_4$$ SC South African Companies ⬤ Affiliation 17 13 150 Sw Southern women 2 ⬤ Interaction 15 14 164 MT Taro exchange ⬤ HumanSocial 22 78 546 CU Contiguous USA ⬤ Infrastructure 49 107 2,458 ZA Zachary karate club ⬤ HumanSocial 34 78 3,500 BC Corporate Leadership ⬤ Affiliation 64 99 3,782 HT Highland tribes ⬤ HumanSocial 16 58 3,928 TF Twitter (MPI) ⬤ Social 52,579,682 1,963,263,821 TW Twitter (WWW) ⬤ Social 41,652,230 1,468,365,182 BM Club membership ⬤ Affiliation 65 95 4,186 MP PDZBase ⬤ Metabolic 212 244 5,656 MR Rhesus ⬤ Animal 16 111 8,274 ET Euroroad ⬤ Infrastructure 1,174 1,417 14,494 Ar American Revolution ⬤ Affiliation 277 160 14,872 MH Highschool ⬤ HumanSocial 70 366 19,876 MK Kangaroo ⬤ Animal 17 91 21,134 MZ Zebra ⬤ Animal 27 111 23,254 MC Crime ⬤ Interaction 2,209 1,476 23,424 CR Chicago ⬤ Infrastructure 1,467 1,298 25,512 Ml Les Misérables ⬤ Misc 77 254 33,116 Mt Train bombing ⬤ HumanContact 64 243 41,134 Ms Sampson ⬤ HumanSocial 18 189 42,576 AN David Copperfield ⬤ Lexical 112 425 43,198 Mp Protein ⬤ Metabolic 1,870 2,277 56,522 MI Physicians ⬤ HumanSocial 241 1,098 59,270 MA Cattle ⬤ Animal 28 217 70,682 TC Air traffic control ⬤ Infrastructure 1,226 2,615 74,868 Mv Dutch college ⬤ HumanSocial 32 3,062 77,198 UL Unicode languages ⬤ Feature 1,122 1,255 86,712 Mc Sheep ⬤ Animal 28 250 112,726 MB Bison ⬤ Animal 26 314 115,036 MW Windsurfers ⬤ HumanContact 43 336 120,268 MX Seventh graders ⬤ HumanSocial 29 376 126,596 MS Human protein (Stelzl) ⬤ Metabolic 1,706 6,207 333,742 MO Residence hall ⬤ HumanSocial 217 2,672 432,370 MV Human protein (Vidal) ⬤ Metabolic 3,133 6,726 449,262 ME Adolescent health ⬤ HumanSocial 2,539 12,969 561,714 PM Caenorhabditis elegans ⬤ Metabolic 453 4,596 723,054 A@ U. Rovira i Virgili ⬤ Communication 1,133 5,451 745,290 Mh Hens ⬤ Animal 32 496 923,552 MQ Macaques ⬤ Animal 62 1,187 2,345,978 MF Human protein (Figeys) ⬤ Metabolic 2,239 6,452 2,761,428 FW Florida ecosystem wet ⬤ Trophic 128 2,106 2,880,586 DNc DNC emails ⬤ Communication 2,029 39,264 2,954,036 FD Florida ecosystem dry ⬤ Trophic 128 2,137 3,018,464 EF Facebook (NIPS) ⬤ Social 2,888 2,981 3,054,614 JZ Jazz musicians ⬤ HumanSocial 198 2,742 3,669,860 ML Little Rock Lake ⬤ Trophic 183 2,494 4,063,016 MN Bible ⬤ Lexical 1,773 16,401 4,065,918 HY Hypertext 2009 ⬤ HumanContact 113 20,818 4,883,008 SX Sexual escorts ⬤ Rating 26,836 50,632 5,157,078 WR Writers ⬤ Authorship 224,925 144,340 5,804,216 CH Chess ⬤ Interaction 7,301 65,053 6,216,178 TL Twitter lists ⬤ Social 23,370 33,101 6,316,466 GN Gnutella ⬤ Computer 62,586 147,892 6,908,208 OR Orkut ⬤ Social 3,072,441 117,184,899 HA Haggle ⬤ HumanContact 274 28,244 7,261,908 PW Prosper.com ⬤ Interaction 25,697 35,377 8,227,890 Shf Hamsterster friendships ⬤ Social 1,858 12,534 8,492,828 PG Pretty Good Privacy ⬤ OnlineContact 10,680 24,316 9,875,476 AS Route views ⬤ Computer 6,474 13,895 10,573,320 Sh Hamsterster full ⬤ Social 2,426 16,631 12,668,530 RM Reality Mining ⬤ HumanContact 96 1,086,404 12,881,442 RA Manufacturing emails ⬤ Communication 167 82,927 13,812,896 CC Cora citation ⬤ Citation 23,166 91,500 14,506,806 Pi DBLP ⬤ Citation 12,591 49,743 14,856,972 ST Movies ⬤ Feature 233,283 281,396 15,295,024 FO FOLDOC ⬤ Hyperlink 13,356 125,207 17,149,830 RD Pennsylvania ⬤ Infrastructure 1,088,092 1,541,898 17,908,880 PR Producers ⬤ Authorship 236,510 207,268 20,396,460 Mti MovieLens t-i ⬤ Folksonomy 40,657 95,580 20,740,224 R1 Texas ⬤ Infrastructure 1,379,917 1,921,660 21,821,436 PS Prosper.com ⬤ Affiliation 14,177 21,017 22,497,618 RO California ⬤ Infrastructure 1,965,206 2,766,607 31,612,286 RE Reuters ⬤ Text 1,846,441 96,903,520 AD Advogato ⬤ Social 6,541 51,127 41,442,262 SD Slashdot ⬤ Communication 51,083 140,778 42,200,498 Mut MovieLens u-t ⬤ Folksonomy 24,546 95,580 45,103,872 Mg Blogs ⬤ Hyperlink 1,224 19,025 46,769,586 CA Amazon (MDS) ⬤ Misc 334,863 925,872 65,863,072 GP Google+ ⬤ Social 23,628 39,242 77,904,048 IN CAIDA ⬤ Computer 26,475 53,381 78,030,634 DN DNC emails co-recipients ⬤ OnlineContact 2,029 136,602 87,111,450 Mui MovieLens u-i ⬤ Folksonomy 15,619 95,580 102,152,360 AM Actor movies ⬤ Affiliation 639,286 1,470,404 188,903,364 BK Brightkite ⬤ Social 58,228 214,078 241,167,376 Bx BookCrossing (ratings) ⬤ Rating 341,559 433,652 336,304,276 AP arXiv astro-ph ⬤ Coauthorship 18,771 198,050 410,726,012 PHc arXiv hep-ph ⬤ Citation 34,546 421,578 418,161,514 EL Wikipedia elections ⬤ OnlineContact 7,118 103,675 518,446,466 LO Location ⬤ Feature 397,589 293,697 522,254,610 CD DBLP co-authorship ⬤ Coauthorship 317,080 1,049,866 530,084,528 CS CiteSeer ⬤ Citation 384,413 1,751,463 533,442,606 Am Amazon (TWEB) ⬤ Misc 403,394 3,387,388 579,017,252 RL Record labels ⬤ Affiliation 355,095 233,286 588,686,820 GH Github ⬤ Authorship 233,905 440,237 620,327,470 FR Friendster ⬤ Social 68,349,466 2,586,147,869 THc arXiv hep-th ⬤ Citation 27,770 352,807 658,699,062 SZ Slashdot Zoo ⬤ Social 79,120 515,397 660,096,934 TO Internet topology ⬤ Computer 34,761 171,403 776,736,356 Dj JUNG dependency ⬤ Software 6,120 138,706 839,662,564 DJ JDK dependency ⬤ Software 6,434 150,985 873,958,984 Pa DBLP ⬤ Authorship 6,851,776 8,649,016 923,863,916 EU EU institution ⬤ Communication 265,214 420,045 929,258,758 EN Enron ⬤ Communication 87,273 1,148,072 942,178,964 SO Stack Overflow ⬤ Rating 1,187,072 1,301,942 971,310,588 PL Pokec ⬤ Social 1,632,803 30,622,564 LJ LiveJournal ⬤ Social 4,847,571 68,475,391 If Infectious ⬤ HumanContact 410 17,298 851,762 Cui CiteULike u-i ⬤ Folksonomy 777,199 2,411,819 1,384,098,060 TM Teams ⬤ Affiliation 1,836,793 1,366,466 1,434,091,924 Ol Facebook (WOSN) ⬤ Social 63,731 817,035 1,499,776,526 OC Occupation ⬤ Affiliation 356,884 250,945 1,537,212,834 DL Wikipedia, English ⬤ Hyperlink 18,268,992 172,183,984 ES Epinions ⬤ Social 75,879 508,837 1,630,702,496 M1 MovieLens 100k ⬤ Rating 3,568 100,000 1,838,200,228 Cut CiteULike u-t ⬤ Folksonomy 198,707 2,411,819 1,946,141,506 GC Google.com internal ⬤ Hyperlink 15,763 171,206 2,105,828,990 Vui vi.sualize.us u-i ⬤ Folksonomy 529,646 2,298,816 2,113,369,668 GW Gowalla ⬤ Social 196,591 950,327 2,336,722,510 BX BookCrossing (implicit) ⬤ Rating 551,079 1,149,739 2,613,565,786 Lk Linux kernel mailing list replies ⬤ Communication 63,399 1,096,440 2,669,048,812 AR Amazon ratings ⬤ Rating 5,523,029 5,838,041 2,807,043,116 Pc DBLP ⬤ Coauthorship 1,314,050 18,986,618 2,832,418,252 LK Linux kernel mailing list threads ⬤ Interaction 421,599 1,565,683 4,099,266,604 PC US patents ⬤ Citation 3,774,768 16,518,947 4,111,412,794 RC Reactome ⬤ Metabolic 6,327 147,547 4,255,595,272 WC Wikipedia (en) ⬤ Feature 3,889,933 3,795,796 4,888,065,352 Vut vi.sualize.us u-t ⬤ Folksonomy 116,279 2,298,816 4,997,987,030 GE DBpedia genre ⬤ Feature 525,651 463,497 5,761,771,762 HY Hyves ⬤ Social 1,402,673 2,777,419 6,176,668,782 But BibSonomy u-t ⬤ Folksonomy 216,261 2,555,080 6,409,052,574 EP Epinions ⬤ Social 131,828 841,372 6,453,318,352 GO Google ⬤ Hyperlink 875,713 5,105,039 7,234,914,630 ND Notre Dame ⬤ Hyperlink 325,729 1,497,134 8,301,389,128 CY Youtube friendship ⬤ Social 1,134,890 2,987,624 9,654,097,656 LM Livemocha ⬤ Social 104,103 2,193,083 13,131,821,918 Lj LiveJournal links ⬤ Social 5,204,176 49,174,464 LG LiveJournal ⬤ Affiliation 13,891,479 112,307,385 LX Linux ⬤ Software 30,837 213,954 1,951,074,894 Us Wikipedia, simple en (dynamic) ⬤ Hyperlink 100,312 1,627,472 3,276,402,818 Up Wikipedia, pl (dynamic) ⬤ Hyperlink 1,033,050 25,026,208 Ud Wikipedia, nl (dynamic) ⬤ Hyperlink 1,039,252 20,070,561 Ui Wikipedia, it (dynamic) ⬤ Hyperlink 1,204,009 34,826,283 Uf Wikipedia, fr (dynamic) ⬤ Hyperlink 2,212,682 59,008,831 Ug Wikipedia, de (dynamic) ⬤ Hyperlink 2,166,669 86,337,879 TR TREC (disks 4–5) ⬤ Text 2,285,379 151,632,178 FX Flixster ⬤ Social 2,523,386 7,918,801 10,593,071,934 R2 Reuters-21578 ⬤ Text 81,791 1,464,182 23,309,665,440 Lb Last.fm band ⬤ Interaction 176,061 19,150,868 38,918,474,416 DBT TV Tropes ⬤ Feature 216,508 3,232,134 39,661,411,392 DF Digg friends ⬤ Social 279,630 1,731,653 42,186,797,872 Dut Delicious ut ⬤ Folksonomy 6,178,261 301,186,579 Dui Delicious ui ⬤ Folksonomy 35,444,383 301,186,579 Dti Delicious ti ⬤ Folksonomy 42,801,712 301,183,605 PL Prosper loans ⬤ Interaction 89,269 3,394,979 35,901,340,680 CN Countries ⬤ Affiliation 1,182,526 637,134 45,201,226,056 Bui BibSonomy u-i ⬤ Folksonomy 779,035 2,555,080 51,365,102,888 CO Wikipedia conflict ⬤ OnlineContact 118,100 2,917,785 64,440,643,864 Ds Discogs label–style ⬤ Feature 487,911 5,255,950 65,147,206,418 Dl Discogs ⬤ Affiliation 3,780,417 14,414,659 78,312,501,992 Bti BibSonomy t-i ⬤ Folksonomy 1,176,793 2,555,080 83,203,483,378 Cti CiteULike t-i ⬤ Folksonomy 1,038,323 2,411,819 90,596,413,384 Dr Discogs label–genre ⬤ Feature 541,557 4,147,665 95,812,257,190 WT TREC WT10g ⬤ Hyperlink 1,601,787 8,063,026 118,288,933,500 SF Stanford ⬤ Hyperlink 281,903 2,312,497 122,314,986,204 M2 MovieLens 1M ⬤ Rating 15,786 1,000,209 135,780,401,238 Vti vi.sualize.us t-i ⬤ Folksonomy 659,472 2,298,816 140,005,809,036 YD Yahoo advertisers ⬤ Lexical 653,260 2,931,708 159,458,026,208 WU WebUni Magdeburg ⬤ Text 212,552 3,869,707 176,869,111,720 DV Digg votes ⬤ Rating 282,371 3,018,197 248,779,120,872 FI Flickr ⬤ Misc 105,938 2,316,948 281,065,304,028 FG Flickr ⬤ Affiliation 895,589 8,545,307 321,104,865,090 Ls Last.fm song ⬤ Interaction 1,086,604 19,150,868 347,084,940,232 PH arXiv hep-ph ⬤ Coauthorship 28,093 4,596,803 565,811,998,438 SK Skitter ⬤ Computer 1,696,415 11,095,298 566,262,437,464 Sd Dogster ⬤ Social 426,820 8,546,581 617,112,529,322 CL Actor collaborations ⬤ Misc 382,219 33,115,812 718,089,033,442 TH arXiv hep-th ⬤ Coauthorship 22,908 2,673,133 749,402,442,684 EX Wikipedia (en) ⬤ Text 279,519 7,846,807 919,423,043,352 DB DBpedia ⬤ Misc 3,966,924 13,820,853 949,680,166,216 BS Berkeley/Stanford ⬤ Hyperlink 685,230 7,600,595 1,128,891,915,348 WT Web trackers ⬤ Hyperlink 68,087,704 140,613,762 Tnl Wikipedia talk, Dutch ⬤ Communication 225,749 1,554,699 39,640,359,028 Tru Wikipedia talk, Russian ⬤ Communication 457,017 2,282,055 137,604,283,760 HUr Hudong related ⬤ Hyperlink 2,452,715 18,854,882 148,775,753,434 HUi Hudong internal ⬤ Hyperlink 1,984,484 14,869,484 Tpt Wikipedia talk, Portuguese ⬤ Communication 541,355 2,424,962 408,898,646,862 Dt Discogs artist–style ⬤ Feature 3,236,269 24,085,580 1,284,657,683,652 ER Epinions ⬤ Rating 996,744 13,668,320 1,639,442,650,152 Tar Wikipedia talk, Arabic ⬤ Communication 1,095,799 1,913,103 1,825,747,539,904 WK Wikipedia, English ⬤ Communication 2,394,385 5,021,410 W2 WikiSigned ⬤ OnlineContact 138,592 740,397 2,991,456,962 Wru Wikipedia links, ru ⬤ Hyperlink 2,853,118 82,056,101 LI Libimseti.cz ⬤ Social 220,970 17,359,346 2,130,083,301,436 BAr Baidu related ⬤ Hyperlink 415,641 3,284,387 2,143,022,830,232 BAi Baidu internal ⬤ Hyperlink 2,141,300 17,794,839 YT YouTube ⬤ Social 3,223,589 9,375,374 YG YouTube ⬤ Affiliation 218,563 293,360 381,648,116 LY Youtube links ⬤ Social 1,138,499 4,942,297 9,637,401,158 YS Yahoo songs ⬤ Rating 2,626,941 256,804,235 WO WordNet ⬤ Lexical 146,005 656,999 408,174,894 Ten Wikipedia talk, English ⬤ Communication 2,987,535 24,981,163 Tde Wikipedia talk, German ⬤ Communication 519,403 6,729,794 187,711,464,036 Tes Wikipedia talk, Spanish ⬤ Communication 497,446 2,702,879 284,138,127,786 Tit Wikipedia talk, Italian ⬤ Communication 863,846 3,067,680 496,562,923,582 Tzh Wikipedia talk, Chinese ⬤ Communication 1,219,241 2,284,546 1,869,969,123,320 J2 Jester 150 ⬤ Rating 101,524 1,728,847 2,212,223,162,138 Tfr Wikipedia talk, French ⬤ Communication 1,420,367 4,641,928 2,589,877,992,672 LF Flickr links ⬤ Social 1,715,255 15,551,250 3,483,825,597,342 Da Discogs artist–genre ⬤ Feature 3,509,661 19,033,891 3,745,144,849,158 FL Flickr ⬤ Social 2,302,925 33,140,017 5,792,259,539,552 Fr Filmtipset ⬤ Rating 225,153 19,554,219 Ff Filmtipset ⬤ Social 39,199 87,415 13,666,118 Ow Facebook ⬤ Communication 46,952 876,993 27,812,668 Fc Filmtipset ⬤ Interaction 104,890 1,266,753 23,774,988,546 it Wikipedia (it) ⬤ Authorship 2,531,261 26,241,217 mfr Wiktionary (fr) ⬤ Authorship 1,917,281 7,399,298 bfr Wikibooks (fr) ⬤ Authorship 33,881 201,727 452,733,850 es Wikipedia (es) ⬤ Authorship 3,623,742 27,011,506 nfr Wikinews (fr) ⬤ Authorship 27,954 193,618 939,454,358 fr Wikipedia (fr) ⬤ Authorship 4,598,826 46,168,355 men Wiktionary (en) ⬤ Authorship 2,163,240 8,998,641 qen Wikiquote (en) ⬤ Authorship 137,970 549,210 3,405,969,028 nen Wikinews (en) ⬤ Authorship 184,536 901,416 6,409,837,346 en Wikipedia (en) ⬤ Authorship 29,143,573 266,769,613 ben Wikibooks (en) ⬤ Authorship 200,108 1,164,576 7,019,722,282 mde Wiktionary (de) ⬤ Authorship 157,806 1,229,501 89,606,310,540 de Wikipedia (de) ⬤ Authorship 4,046,832 57,323,775 DO Dolphins ⬤ Animal 62 159 6,234 DB Douban ⬤ Social 154,908 327,162 53,636,092 EA Edinburgh Associative Thesaurus ⬤ Lexical 23,132 511,764 255,613,548 Wpt Wikipedia links, pt ⬤ Hyperlink 1,603,222 49,021,409 6,033,394,188,086 Wpl Wikipedia links, pl ⬤ Hyperlink 1,529,135 57,489,447 Wja Wikipedia links, ja ⬤ Hyperlink 1,610,638 71,055,717 4,502,336,616,982 Wit Wikipedia links, it ⬤ Hyperlink 1,865,965 91,555,008 Wfr Wikipedia links, fr ⬤ Hyperlink 3,023,165 102,382,410 Wen Wikipedia links, en ⬤ Hyperlink 12,150,976 378,142,420 Wde Wikipedia links, de ⬤ Hyperlink 3,225,565 81,626,917 WP Wikipedia, English ⬤ Hyperlink 1,870,709 39,953,145 WD Wikipedia Threads (de) ⬤ Communication 91,340 2,435,731 9,652,669,352 Sc Catster ⬤ Social 149,700 5,449,275 3,623,072,057,374 Scd Catster/Dogster ⬤ Social 623,766 15,699,276 6,438,307,141,540 OG Orkut ⬤ Affiliation 14,297,249 327,037,487 SW Southern women 1 ⬤ Interaction 50 89 5,050 UG US power grid ⬤ Infrastructure 4,941 6,594 96,752 UF UC Irvine forum ⬤ Interaction 2,320 33,720 1,322,222 AC arXiv cond-mat ⬤ Authorship 55,467 58,595 2,095,390 UC UC Irvine messages ⬤ Communication 1,899 59,835 8,883,716 DG Digg ⬤ Communication 30,398 87,627 9,980,426 OF OpenFlights ⬤ Infrastructure 2,939 30,501 24,600,706 OF OpenFlights ⬤ Infrastructure 3,425 67,663 38,875,116 AF US airports ⬤ Infrastructure 1,574 28,236 164,530,266 NX Netflix ⬤ Rating 978,148 100,480,507 Ws Twitter (ICWSM) ⬤ Social 465,017 834,797 928,253,108 Wui Twitter u-i ⬤ Folksonomy 9,618,743 12,656,613 3,286,104,890 Wa Twitter ⬤ OnlineContact 2,919,613 12,887,063 3,610,479,352 Wut Twitter u-t ⬤ Folksonomy 880,846 4,664,605 5,682,999,878 Wti Twitter t-i ⬤ Folksonomy 1,773,193 2,635,885 18,239,948,076 M3 MovieLens 10M ⬤ Rating 150,433 10,000,054 9,736,390,797,092 J1 Jester 100 ⬤ Rating 146,942 4,136,360 21,209,254,824,380