{"entities":{"Q2062885":{"pageid":2073627,"ns":120,"title":"Item:Q2062885","lastrevid":82434530,"modified":"2026-05-06T20:54:00Z","type":"item","id":"Q2062885","labels":{"en":{"language":"en","value":"On the proper arc labeling of directed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7451435"}},"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":"Q2062885$0E428D39-215F-4394-B504-910DE5033BFE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b10835e6822bac3c302191f9d306fd92efa89cff","datavalue":{"value":{"text":"On the proper arc labeling of directed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2062885$BAB8DD95-E422-46A4-886C-1BCC9C7F663E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"005aca04728b3acb7795860a68d54206115c8543","datavalue":{"value":"1480.05110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$4166FCB2-4A09-406C-89EA-2D0865112618","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3eea36a96bc132d1b7fecd7ccf4b7c23b3fcd079","datavalue":{"value":{"entity-type":"item","numeric-id":326465,"id":"Q326465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$FB57FA36-27A1-4E7F-BAF2-E87852121478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e330a996c066e977d1217626b9d2eb9c57ced77e","datavalue":{"value":{"entity-type":"item","numeric-id":300223,"id":"Q300223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$AC514F04-E42E-4F19-8927-DE6348CB793C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$F5FA74DD-25BD-4460-B13E-4C3D47ABC474","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"af49efd26010b4160b051c86a282dcb3745069b3","datavalue":{"value":{"time":"+2022-01-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2062885$D6BF787A-E121-426D-80CC-427E1DFFADC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"06c06c4125aeca2727cd355f428793bd139a337b","datavalue":{"value":"An arc labeling $l$ of a directed graph $G$ with positive integers is proper if for any two adjacent vertices $v$, $u$, $S_l (v)\\neq S_l (u)$, where $S_l (v)$ denotes the sum of labels of the arcs with head $v$. The proper arc labeling number of a directed graph $G$, denoted by $\\chi_p(G)$, is $\\min_l\\in\\Gamma\\max_{(v\\in V(G))}S_l(v)$, where $\\Gamma$ is the set of proper arc labelings of $G$. A proper arc labeling $l$ of $G$ is optimal if $\\max_{(v\\in V(G))}S_l(v)=\\chi_p(G)$. In this paper, the authors study the proper arc labeling number of graphs and present some lower and upper bounds. They prove that every directed graph $G$ has a (not necessarily optimal) proper arc labeling from $\\{1,2,3\\}$; every graph $G$ has an optimal proper arc labeling from $\\{1,2,\\dots,r+1\\}$, where $r=\\max\\{\\lceil(d_G^+ (v))/(d_G^-(V))\\rceil+1:v\\in V(G)\\}$; if $G$ is a bipartite graph, then $\\Delta^-(v)\\leq\\chi_p (G)\\leq\\Delta^-(v)+1$; for each constant number $c$, there is a directed tree $T$ such that it does not have any optimal proper arc labeling from $\\{1,2,\\dots,c\\}$. Also, they show that there is a polynomial time algorithm to find the proper arc labeling number of directed trees. Further, they compute that the proper arc labeling number of planar directed graphs is NP-hard. Finally, they pose open problems for further research.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062885$0478BBCA-2FD5-433F-953B-249DD921CB6F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"88eda1777367c20713bc1f4f072e3698ad4c1952","datavalue":{"value":{"entity-type":"item","numeric-id":240267,"id":"Q240267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$DEDF8967-980C-4BB9-B46C-CE25B9A5C1C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$8B8D092F-6035-40C4-8179-C3AF9A6DAA33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$CF64A7BE-0C17-4A57-B673-16C90BB8F951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$8A5B0753-2DF8-48D7-9C95-F940836A90F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$749ACB56-4EE5-4D9D-9579-774981D74470","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ff07d194083a4069988e1afebf5c3d119b808805","datavalue":{"value":"7451435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$4EFCE2C6-22DF-4BCF-8673-8CBFAE52E55D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1145f0d02fdb2d129e4d23628ca916a4130d0836","datavalue":{"value":"proper orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062885$DBD4192C-7D9E-4A01-A288-3BD2AC778A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"837f854130f6442d9865ab95fa28c854e5ba763d","datavalue":{"value":"proper arc labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062885$C532F49D-2CCD-4278-A87E-6D81D4BA42B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1e818aab55c9bc880ddf7326b881d8fe9e06710","datavalue":{"value":"proper arc labeling number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062885$65055CC8-F873-4C93-AD4F-F13EB913CD23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab139098a392e0e6fd5b54e16f4eb20bb1787c19","datavalue":{"value":"optimal proper arc labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062885$F119FFB6-30B2-47DC-B041-048E8BC0C94C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062885$F2987685-52D5-4C86-9CC2-26B44518BEB6","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":"Q2062885$5F7F1A4A-1B8E-4323-8BD7-5558DA6A99B9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb63339994f2b5f4086af20a0f7c01e143656e99","datavalue":{"value":"https://doi.org/10.1007/s00373-021-02435-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q2062885$33270424-0F92-4343-8829-647A6C6FD298","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d2cf3b10cfc437eeee23bcab31f259c5eecd330f","datavalue":{"value":"W4200289184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$C2A189CA-6952-4743-A753-9B5297267A82","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"00886c5bd7c9b5d1d32a8d0cc540dbfa6298e759","datavalue":{"value":{"entity-type":"item","numeric-id":2445254,"id":"Q2445254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$1D5DBE4A-C1A0-4DAB-9880-A5AB8A33A6CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e30fb325e316ac0e7f0458e295d051d449dd2ff","datavalue":{"value":{"entity-type":"item","numeric-id":1680487,"id":"Q1680487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$F6050FAF-2464-4A07-B666-456E1A0AEBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81768e2c633a39c2fe1709e93d719fce68e7be68","datavalue":{"value":{"entity-type":"item","numeric-id":5066921,"id":"Q5066921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$4ED5D987-6D7B-49A1-AFB9-FCE5AA260686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a17d95e32be2b50de12dfc9653c7fe926c9d84","datavalue":{"value":{"entity-type":"item","numeric-id":820574,"id":"Q820574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$21C7721D-CAF3-433E-9FD1-9BAFE5F5A315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"316224a388fa5a6273c05f3cc9629b7a5cbce458","datavalue":{"value":{"entity-type":"item","numeric-id":484321,"id":"Q484321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$6F2CFEFC-0F5A-4184-BD19-FFA9E2B53BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"417f695b02aa947ed9327c29e3ce72d6b20958a4","datavalue":{"value":{"entity-type":"item","numeric-id":301589,"id":"Q301589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$54814DA8-6DA5-4DB3-B409-1991534A5524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef8c292cdf01fde59abf701b34dee0e36651e19","datavalue":{"value":{"entity-type":"item","numeric-id":2632010,"id":"Q2632010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$6B605071-21A3-4861-9E91-748112419F04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dd18c02bfef88685f790b0f55f850425bccaf8c","datavalue":{"value":{"entity-type":"item","numeric-id":2043367,"id":"Q2043367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$0D4E451C-73E7-472E-AC29-3871C6E688A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13742702b6cf9c1b444e751fe20b81d1129f239c","datavalue":{"value":{"entity-type":"item","numeric-id":2663989,"id":"Q2663989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$F649155E-F1B2-46BE-8984-256610049FA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b19ce13032ffe1861bcc3af7e7f1de38245e533","datavalue":{"value":{"entity-type":"item","numeric-id":497328,"id":"Q497328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$46B70D5A-174F-4350-9BF6-05181E0B169C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d7b187840c723db320aff82b6bbe6f261cb59a3","datavalue":{"value":{"entity-type":"item","numeric-id":2662560,"id":"Q2662560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$E33A4CE8-9EF5-42E5-86B5-578FFA651E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21f73a67756d8958437396bbd33ecf8f1e318cdf","datavalue":{"value":{"entity-type":"item","numeric-id":1684937,"id":"Q1684937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$0CB0934D-4C8D-40B4-8BB5-2FD6256BC9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b44ce04da2a775b0d06ca017d31794e60c51a0","datavalue":{"value":{"entity-type":"item","numeric-id":2181231,"id":"Q2181231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$1C4EAAFF-BDE5-422A-983F-F435FAB28B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5325820f1da9bdbe993d9d54d34a90dc88d69e8e","datavalue":{"value":{"entity-type":"item","numeric-id":4869540,"id":"Q4869540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062885$3C9FFA3F-0BF1-41A6-9E6B-0A63826104A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26fd33574dfe7deaf2be0555747b093efd589076","datavalue":{"value":"10.1007/S00373-021-02435-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062885$8B811941-6842-40D4-9E8A-1F5809198F48","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a384fb87669ebd3e933638d12d54f114f39d0fa","datavalue":{"value":{"entity-type":"item","numeric-id":5251963,"id":"Q5251963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27ddcf0e226b47ee6a7174feda819891553fa603","datavalue":{"value":{"amount":"+0.7933375239372253","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":"Q2062885$C656F92B-9F2A-448A-8DE3-2D2F3E93151C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae952c6d92310a34b45e3cfb94425c8542380cb4","datavalue":{"value":{"entity-type":"item","numeric-id":1693177,"id":"Q1693177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0804e9a523a1ce751c6f74aa675ed5a983ff86c","datavalue":{"value":{"amount":"+0.7739324569702148","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":"Q2062885$647EA370-CDCA-4FDC-B4DE-F99ECE62B5AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ffececaeb0f2af3894f8405aaf057dbb7f00158","datavalue":{"value":{"entity-type":"item","numeric-id":1271877,"id":"Q1271877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1254004fcf213e63f76bed969f5c4dac77753a9a","datavalue":{"value":{"amount":"+0.77037513256073","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":"Q2062885$AE4A13AA-6E74-47EA-BBDF-8B32DE93436A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3f9c8a3804668ac427fa95d2c0808615a7fe712","datavalue":{"value":{"entity-type":"item","numeric-id":391137,"id":"Q391137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"722e2b87ea1a1ad9294f91ff531c413a8990d097","datavalue":{"value":{"amount":"+0.7642547488212585","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":"Q2062885$F78FA8CE-D243-402C-B0C4-C20F1BBE958F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d93ebb7f5492fcd46a2ae36accb6de372c7a0a2","datavalue":{"value":{"entity-type":"item","numeric-id":881579,"id":"Q881579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bc186d939b40fe7f8223a2df975e86302aeec79","datavalue":{"value":{"amount":"+0.7582185864448547","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":"Q2062885$2EBE1637-8B7C-4D26-97B5-F91CA2AD730A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the proper arc labeling of directed graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_proper_arc_labeling_of_directed_graphs"}}}}}