{"entities":{"Q708427":{"pageid":710276,"ns":120,"title":"Item:Q708427","lastrevid":63786786,"modified":"2026-04-11T15:32:57Z","type":"item","id":"Q708427","labels":{"en":{"language":"en","value":"Characterizing paths as \\(m\\)-step competition graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5798557"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$1138C1F4-7BA9-40B8-9FB5-BF397FC3D3BC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"52e6fbca8286023bc7e2d4942da9478186415617","datavalue":{"value":{"text":"Characterizing paths as \\(m\\)-step competition graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q708427$F6E5D5E4-B71D-4FDD-9600-6FB54FCB9D17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52ce2089179b292259a376cd6ab7456a2f794e3a","datavalue":{"value":"1206.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708427$3A07F070-0FFA-426A-9EF3-58B7D58EEA27","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"11939d52f842920b7a3b52934c50989b2cea14e7","datavalue":{"value":{"entity-type":"item","numeric-id":708426,"id":"Q708426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$71F51E8A-6A88-46A1-9F30-2794921596A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"40948602474792de3fe33fbc906e677c2de62f40","datavalue":{"value":{"entity-type":"item","numeric-id":942104,"id":"Q942104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$D8754DD8-B1D8-4CC9-94CC-245FFE5739B5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$B9508EF7-191B-4E1A-ABA2-A6AA3AB6974A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f64b28384ad68ec83e16fec2c0efbccc5663b19","datavalue":{"value":{"time":"+2010-10-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q708427$DF65E4CB-2141-4EEE-839D-F2D03935D0D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23d8217058da286b472de37093e30920b666faec","datavalue":{"value":"Let \\(D\\) be a digraph and \\(x\\) be a vertex of \\(D\\). Then \\(N_{m}(x)\\) denotes the set of all vertices \\(y\\) of \\(D\\) such that there is an \\(m\\)-step walk from \\(x\\) to \\(y\\). Two vertices \\(x\\) and \\(y\\) of \\(D\\) are said to be in \\(m\\)-step competition if \\(N_{m}(x)\\cap N_{m}(y)\\neq \\varnothing \\). The \\(m\\)-step competition of \\(D\\) is the simple graph \\(C^{m}(D)\\) in which the vertex set is the same vertex set as \\(D\\) and \\(xy\\) is an edge if and only if \\(x\\) and \\(y\\) are in \\(m\\)-step competition in \\(D\\).  \\textit{H. H. Cho}, \\textit{S.-R. Ki,}, and \\textit{Y. Nam} [``The \\(m\\)-step competition graph of a digraph,'' Discrete Appl. Math. 105, No.\\,1-3, 115--127 (2000; Zbl 0966.05066)] proved that \\(P_{n}\\), the path on \\(n\\) vertices, is a \\(2\\)-step competition graph. \\textit{G. T. Helleloid} [''Connected triangle-free \\(m\\)-step competition graphs,'' Discrete Appl. Math. 145, No.\\,3, 376--383 (2005; Zbl 1066.05120)] proved that \\(P_{n}\\) is an \\((n-1)\\)- and \\((n-2)\\)-step competition graph and that \\(P_{n}\\) is an \\(m\\)-step competition graph for \\(m \\geq n>3\\). This paper is a continuation of the above works in which the authors proved that if \\(m\\) divides \\(n-1\\) or \\(n-2\\), then \\(P_{n}\\) is an \\(m\\)-step competition graph and that if \\(n \\geq 6\\) and \\(\\frac{n}{2} \\leq m \\leq n-3\\), then \\(P_{n}\\) is not an \\(m\\)-step competition graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q708427$19DAFFF2-030F-4211-8793-18EE0FC9D407","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708427$0D9D2C0B-DDE9-4C83-BD75-2E30D5928190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708427$12C8E5B1-9BC1-4F50-9C18-7628457561F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708427$A3C24597-2332-4DAE-AE9B-8885FE02785B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d746524e0e388cd22313f2f3f5ec2e877228929d","datavalue":{"value":"5798557","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708427$F70ED4D2-9CE4-4CB5-A6A7-9537A03B010B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e457a66abb343cfd309ba9c6aaaa8594713f9c6","datavalue":{"value":"m-step competition","type":"string"},"datatype":"string"},"type":"statement","id":"Q708427$C55219BA-F55C-4448-9A00-881C15B9EC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q708427$135A4173-300E-4F30-9D1C-ACC51331A52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65bd34070aaf54b27536b874611d93a4ce51fc08","datavalue":{"value":"walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q708427$A69BC86D-E612-4D0B-83FC-A0C6083CA3CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q708427$D8CF2E40-1274-41B3-8F57-406215CA430C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f83e4bebf98cf99c2d8d57f00b8fd14157b2c915","datavalue":{"value":{"entity-type":"item","numeric-id":625388,"id":"Q625388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$18D60CB2-16A6-4063-9A92-21EB2C381BB4","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$4DC7E285-A42A-4727-8B08-2B8FC43CA4B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1da2d8ff2d528d95fce5a4f322be28ac3e0b3934","datavalue":{"value":"https://doi.org/10.1016/j.disc.2010.06.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q708427$773C1649-1CE3-4D47-82A4-96AB93C0EAC8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"338f30dc17170574676d518029ff01a1320fb815","datavalue":{"value":"W2050665246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708427$7937FD13-9668-46F8-AB19-8F0B1B2B7AE2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3d3bd14cc1377caa3e87cb84d6884a1f9bc3106","datavalue":{"value":{"entity-type":"item","numeric-id":1582072,"id":"Q1582072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$80BC1A56-A89E-4960-96E6-4CA3236C6508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08de071c8f8374ab6d124bb2acd9a05d2e29f515","datavalue":{"value":{"entity-type":"item","numeric-id":1765515,"id":"Q1765515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$3371897E-4449-4441-98AB-92820A34FC5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdc17665fdeec924480eea15839315c8a4a91c0d","datavalue":{"value":{"entity-type":"item","numeric-id":2576346,"id":"Q2576346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$3BE739DC-4826-4C68-8B71-8AC522720242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94964cf9342df6aa00175eba294ddb3cec1bc612","datavalue":{"value":{"entity-type":"item","numeric-id":3139771,"id":"Q3139771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$7E2C288A-25EC-4E84-9F05-AAA18993719B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5523823c5d0e4181a19c53d3be41e63b18031dc9","datavalue":{"value":{"entity-type":"item","numeric-id":1377663,"id":"Q1377663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$332F3E6B-7009-44E9-9967-CA5B2D66D00E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b8e3c035843b3caed4c9668dc05a1cd346931d5","datavalue":{"value":{"entity-type":"item","numeric-id":1003747,"id":"Q1003747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$95A996F2-EDF3-4C63-9511-1638886CD460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efd90cba7e52e8909a6095517fb25da71943a3c9","datavalue":{"value":{"entity-type":"item","numeric-id":1028099,"id":"Q1028099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$76FC2B4B-D770-4BBD-A48B-EA2277567432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f09f8df50dc79fd1b10d986b88bd3ae4c667708c","datavalue":{"value":{"entity-type":"item","numeric-id":1026165,"id":"Q1026165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708427$0C8F2F97-05F2-43DE-8722-C2B640345AF1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"48c49d567fcd094b1cf9918649c01772bdfdf0e7","datavalue":{"value":"10.1016/J.DISC.2010.06.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708427$69F54F64-C0E6-465E-9E90-C5DC40E6FBC5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b94eac1c2a5edb41147314246079e80875cf60cf","datavalue":{"value":{"entity-type":"item","numeric-id":642960,"id":"Q642960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46cb3bf09c14f68683ea963c361171eac47e4106","datavalue":{"value":{"amount":"+0.90106606","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$DA920516-6F29-4AE2-94EE-AFB17A8ACA5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9ccd50632b63efdab40f1f5a2ff577e58ea58ca","datavalue":{"value":{"entity-type":"item","numeric-id":2576346,"id":"Q2576346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b51bb7140921c31c780017f14e4ebc52f71d2920","datavalue":{"value":{"amount":"+0.8917904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$174AF63E-1492-4935-96F8-B3F958DED788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c163fe7e12967fbb32cbfb91a121de32c6d5ab90","datavalue":{"value":{"entity-type":"item","numeric-id":1026165,"id":"Q1026165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1049c177e810464ea8085b01a825b4daaa62eeb","datavalue":{"value":{"amount":"+0.8760526","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$2F3AAFD0-066A-40A8-ACE3-1629EBF8777B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66092a081d19169ca3fcbed0d282cb5935870d45","datavalue":{"value":{"entity-type":"item","numeric-id":1582072,"id":"Q1582072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f114ab1afd9c75164db7b0c5538a63749c2e9e0","datavalue":{"value":{"amount":"+0.87220705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$0DA3B0B9-4CD4-421C-AED8-E1E07C852174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35f8cf86d9dea18f0bbddcfead0f2303d51d5016","datavalue":{"value":{"entity-type":"item","numeric-id":617643,"id":"Q617643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b497ba824bc404c4308e4f016da081066fd4a321","datavalue":{"value":{"amount":"+0.8642838","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$1DB6AE5B-A5C5-4947-BBC9-8F9A368631B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16409ba92a8b13a489c6772a10acfbf36d0d96a1","datavalue":{"value":{"entity-type":"item","numeric-id":5405454,"id":"Q5405454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97291dd4fa771b0dbb3119050de77a051590c991","datavalue":{"value":{"amount":"+0.8311645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$1A3BE9B2-C211-486E-9D0F-AA3347E8C3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9716437a5603db0651cc8edb25ea06dee94ad565","datavalue":{"value":{"entity-type":"item","numeric-id":4393335,"id":"Q4393335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ced0dfceec28a4c0cff93096011955a73fece2c7","datavalue":{"value":{"amount":"+0.8147918","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$26F6AEF0-86C1-4223-A05C-A55DECC2F003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"328d6063a71ad3f55d854bc5b8007e984a351169","datavalue":{"value":{"entity-type":"item","numeric-id":4528057,"id":"Q4528057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68b1aee58cc3158d1816ad69ae573b0f8a6a0fb8","datavalue":{"value":{"amount":"+0.80558074","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$0B90A948-8C34-4D73-ADF5-5D83A7FE229A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d61e0455546abd24b22c1bf891b7297986e836e","datavalue":{"value":{"entity-type":"item","numeric-id":3408840,"id":"Q3408840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3890b9137aea035d6b12258c220e5057d7ea2e6","datavalue":{"value":{"amount":"+0.7988379","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$4EEE8E7D-0558-4874-927F-7F40F754DBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"128c612af836f89f0be8439bbcab2a1d3fc1b251","datavalue":{"value":{"entity-type":"item","numeric-id":2053626,"id":"Q2053626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c11529f92d0ccef4c72209872c2917254e8743a","datavalue":{"value":{"amount":"+0.794159","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q708427$FC8FDD89-463D-4BA4-A784-1A626AA2E369","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Characterizing paths as \\(m\\)-step competition graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Characterizing_paths_as_%5C(m%5C)-step_competition_graphs"}}}}}