{"entities":{"Q1849948":{"pageid":1860690,"ns":120,"title":"Item:Q1849948","lastrevid":74248185,"modified":"2026-04-14T19:10:36Z","type":"item","id":"Q1849948","labels":{"en":{"language":"en","value":"Hamiltonian iterated line graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1838935"}},"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":"Q1849948$9147D5DA-44CF-4178-A8BF-BDA206C42634","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"529b45e882179bab0b04facfbdef0443999c678a","datavalue":{"value":{"text":"Hamiltonian iterated line graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1849948$D84FBD5D-70BA-465E-BF53-B6C01E05F029","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"781a6ea2875d5925eef03863cb6a015e5d2a1b65","datavalue":{"value":"1027.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849948$6DC1626A-E5A2-4D4B-835B-DE961BACF23C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3c7380a5d6869ecbe166d9c376583c706ec7330","datavalue":{"value":"10.1016/S0012-365X(01)00442-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849948$EA4A25CD-40BA-406D-ADB7-5894237E7521","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"525d6f09038ca260fa4e58b5f4f617ddc9b28c02","datavalue":{"value":{"entity-type":"item","numeric-id":1849947,"id":"Q1849947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849948$70C4E2C3-7732-423D-BDA5-4BBBE90303FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c65357f75e16295ea90f3accb6bd64543a064607","datavalue":{"value":{"entity-type":"item","numeric-id":230803,"id":"Q230803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849948$0937D2B4-4F26-4A36-BBF3-D13E37E485BE","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":"Q1849948$6B3DD505-0429-4654-9A2E-5CDD5D68070F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82ac30fadc544187fd268bb88e1da4be75a5ee8c","datavalue":{"value":{"time":"+2002-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1849948$19069259-E953-4DD3-AD69-8DC48AB2F049","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8334b388bacdcc536409733903f02976e95e07a","datavalue":{"value":"The Hamiltonian index \\(h(G)\\) of a connected multigraph \\(G\\) other than a path is defined as the minimum integer \\(n\\) such that \\(L^n(G)\\) is Hamiltonian, where \\(L(G)=L^1(G)\\) denotes the line graph of \\(G\\) and \\(L^n(G)=L(L^n(G))\\). A well-known theorem of \\textit{F. Harary} and \\textit{C. S. J. A. Nash-Williams} [Can. Math. Bull. 8, 701-709 (1965; Zbl 0136.44704)] says that \\(h(G)=1\\) iff \\(G\\) has a Eulerian subgraph \\(S\\) such that each edge of \\(G\\) is incident with a vertex of \\(S\\).    In the paper under review, this classical result is extended to a characterization of multigraphs of Hamiltonian index \\(n\\geq 2\\), given in terms of existence of certain Eulerian subgraphs. The main theorem is then used to obtain results that might be helpful when designing an algorithm for finding \\(h(G)\\). While the problem to determine \\(h(G)\\) is known to be NP-hard [\\textit{A. A. Bertossi}, Inf. Process. Lett. 13, 157-159 (1981; Zbl 0495.68058)] in general, the authors conjecture that it can be solved in polynomial time provided \\(h(G)\\geq 2\\).    Another application of the main theorem is an upper bound on \\(h(G)\\), which implies previously published upper bounds on \\(h(G)\\) for multigraphs with minimum degree at least three [\\textit{G. Chartrand} and \\textit{C. E. Wall}, Studia Sci. Math. Hungar. 8(1973), 43-48 (1974; Zbl 0279.05121)] or graphs with maximum degree at least three [\\textit{M. L. Sara\u017ein}, Discrete Math. 134, 85-91 (1994; Zbl 0815.05044)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849948$7A1785BE-F178-45E2-A93C-0A1E6CC2C1DC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c0617d45f23e5dfc7fb0eb4ddcab2f46301293e8","datavalue":{"value":{"entity-type":"item","numeric-id":414470,"id":"Q414470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849948$2A92650E-C756-4F45-B451-3E84EBD794AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849948$315083C7-B0BD-4D4C-81F1-CABD4B83B85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849948$5D458080-325F-4B87-A4B9-F2B1676F20E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd8330548d15c1d1ab6cfc82300289d881f03dfd","datavalue":{"value":"1838935","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849948$0533D5BD-DCF4-4CA3-A7C5-0FC62A3D9CD2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e4517c15c23bd0c01f71af9964a545154951753","datavalue":{"value":"iterated line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849948$C34BE5F5-C771-43AC-95B9-750827073552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94efc1788f4aa4a299526143cd02c852cdc1ba1d","datavalue":{"value":"Eulerian subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849948$E0E0E4CC-BA5A-4EB2-8B0C-DC8F7C75395C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f16930d81a1cf43c563e64336a0f4a21c92225fb","datavalue":{"value":"Hamiltonian index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849948$C48CBAAF-2247-4251-9471-827C58DD8EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"336e94e7da765d10c39ba56a18f8bab11856f5fa","datavalue":{"value":"split block","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849948$09D2CCBC-3367-4FC6-897D-59C4761EE948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd49bf66c7a39975528527a26b9fcda6003a02d7","datavalue":{"value":"contraction of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849948$1F609E82-45BD-4CAC-8649-ECCD612A28A8","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":"Q1849948$3645A3D4-7636-4922-ADF4-E5163319F175","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d98e2a1a76dab228c3e27d354d074354375c686","datavalue":{"value":{"entity-type":"item","numeric-id":3193885,"id":"Q3193885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ec4c1096165c7467c70f898d178dfa7ae690822","datavalue":{"value":{"amount":"+0.8927451372146606","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1849948$C1E61BAC-7BBC-4B0C-B213-8F6439FED9F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4f470879883089dd6051338a3d402e9ea885c72","datavalue":{"value":{"entity-type":"item","numeric-id":1099188,"id":"Q1099188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93b3b80f5a9155efb0c26ef8a029e52e8653bf2d","datavalue":{"value":{"amount":"+0.883579671382904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1849948$B5511629-23CC-4737-8A22-3AB0ADB33E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca1ea7e29c94a06c9461788130da0ee38b496e45","datavalue":{"value":{"entity-type":"item","numeric-id":1313880,"id":"Q1313880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0e62ccc7e3f1b3110361efdcdbb43d4cd3301c8","datavalue":{"value":{"amount":"+0.8786821365356445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1849948$4C65AFBD-E342-4906-91DD-F15238DF249F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e399a870fb773af5a0622afefd698c3333b3a096","datavalue":{"value":{"entity-type":"item","numeric-id":5956112,"id":"Q5956112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31edc7f9799e9a62321fbdc0ebb29a6f79b43321","datavalue":{"value":{"amount":"+0.878253698348999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1849948$0553CE2E-BEFD-48EE-9824-A5AEA214B96E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e34399f0a819c64d826544ef5532a16a637cb88e","datavalue":{"value":{"entity-type":"item","numeric-id":2139786,"id":"Q2139786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6a34d574eac3fdf7221c70193c369d730901506","datavalue":{"value":{"amount":"+0.8622150421142578","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1849948$B6DBC6C7-BA22-4B4D-AF61-87C89FF0F65A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hamiltonian iterated line graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hamiltonian_iterated_line_graphs"}}}}}