{"entities":{"Q879396":{"pageid":881244,"ns":120,"title":"Item:Q879396","lastrevid":65044797,"modified":"2026-04-11T23:57:02Z","type":"item","id":"Q879396","labels":{"en":{"language":"en","value":"Graphs with small boundary"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5151805"}},"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":"Q879396$2A92CCB0-E10A-4784-9908-6D0453FE3988","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b5271ce38a4a63cb600f58ab3529c93ab9bde2c6","datavalue":{"value":{"text":"Graphs with small boundary","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q879396$96ABDEB0-925F-4C8E-848E-4600AD3BCC51","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b2534e73fc6c42ce339ac40efb4da3cc6fa9b92b","datavalue":{"value":"1121.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879396$511DB7B2-C8A9-48DA-9F09-D5FA7C8D0069","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c89b41e77e816ad742c4c8b052b2da5ea6df827","datavalue":{"value":{"entity-type":"item","numeric-id":879395,"id":"Q879395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879396$81C7ECA7-1E2C-4301-AB64-3755DBE498EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea3cb9fe6240a14735eacdd3f47c5ce6de5321a8","datavalue":{"value":{"entity-type":"item","numeric-id":214981,"id":"Q214981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879396$BD780206-DDB4-46ED-B7A6-FA7412E2976F","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":"Q879396$2A8754D2-89A3-4575-9449-1C86E203053F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cbd0eb8b100807c851c8df9ae7f8fa5376f95dfe","datavalue":{"value":{"time":"+2007-05-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":"Q879396$B41C97F7-43D4-462D-89D4-62777A1AF602","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5759f0cb6f9d2120f1fd4d5aa417f1c9f46f1495","datavalue":{"value":"In a graph \\(G\\), a vertex \\(x\\) is a boundary vertex of a vertex \\(y\\) if they belong to the same (connected) component of \\(G\\) and the distance between \\(y\\) and each neighbor of \\(x\\) is at most the distance between \\(y\\) and \\(x\\). A boundary vertex is one that is a boundary vertex of some vertex. The boundary \\(B(G)\\) of \\(G\\) is the set of all boundary vertices in \\(G\\). Every connected graph with at least two vertices has at least two boundary vertices. The authors characterize connected graphs \\(G\\) with at most three boundary vertices as follows: \\(| B(G)| = 2\\) if and only if \\(G\\) is a path, and \\(| B(G)| = 3\\) if and only if \\(G\\) is a claw-like tree or a tripod. (A claw-like tree is a subdivision of the claw \\(K_{1,3}\\), and a tripod is obtained from a triangle \\(H\\) by taking a subset \\(X\\) of vertices of \\(H\\) and for each vertex \\(x\\in X\\), preparing a path \\(P_x\\) and joining \\(x\\) and one of the endvertices of \\(P_x\\).) The authors also prove that the minimum degree of any connected graph \\(G\\) is at most six whenever \\(G\\) has exactly four boundary vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q879396$3A471492-88D4-445F-A344-A23C9E726F1A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879396$6341DEF0-FA87-4B96-A80B-8CB7AAF41B83","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879396$BF8EC381-412B-468B-B7E8-BACC4F037E94","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"20518d5f6f1fce9124c1a3b8b405f35d9875d2fd","datavalue":{"value":"5151805","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879396$15DF73BF-3314-4811-B080-785B2E456599","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55a9a28977a40fa3aa2f3604983953a73e55c354","datavalue":{"value":"Boundary vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q879396$99461546-4387-4FDF-9BCA-5C1910522AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a11624083b4e516dcb154c74becf53e0dbbaa39d","datavalue":{"value":"graph boundary","type":"string"},"datatype":"string"},"type":"statement","id":"Q879396$20873B88-E9A5-440F-B10E-6041C886751F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"919f41300ee1bc2ef274640dbf99566507356cc5","datavalue":{"value":"distance in graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q879396$5129DFE4-D30C-486C-B484-3750FA8D7F5C","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":"Q879396$F3A6B9A2-032F-4865-A1F1-E8F22693CD36","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f4c334c8a3e18ff863de2e6511ca859247cde314","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.09.028","type":"string"},"datatype":"url"},"type":"statement","id":"Q879396$29CC9816-403E-44F3-91CF-10889B7CE9F3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d7b30a32780e1a94ca9acc1ead31f93467224465","datavalue":{"value":"W2001877124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879396$631D644A-33AC-4FD6-841E-857A25E8730D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"baff6e2cb7cb7f37b94d0258ca47efcb3025eb5a","datavalue":{"value":{"entity-type":"item","numeric-id":1869215,"id":"Q1869215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879396$21E193EB-6A28-430F-BAAB-0FBB1ABFF0AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bfdc413c5c2954374598c1504538af32d92e757","datavalue":{"value":{"entity-type":"item","numeric-id":4820810,"id":"Q4820810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879396$A3786B7A-61C1-440B-A08A-8408E753C7A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7540b3e21b08efcbd4aa7197a7a060f4f8771cbe","datavalue":{"value":{"entity-type":"item","numeric-id":4350166,"id":"Q4350166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879396$D70B4432-853B-4FBA-8225-4A3EB205CBC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a510f566f79385d5ca43c692f202f961b59bbed","datavalue":{"value":"10.1016/J.DISC.2006.09.028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879396$7A5C67E4-23EC-428F-95C1-B96177B17EB0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e53a7103ab6216fd6fe60cb64f6c0233df4d733b","datavalue":{"value":{"entity-type":"item","numeric-id":625373,"id":"Q625373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f65fa103c451f60fa9848d1259fa1b77e088921","datavalue":{"value":{"amount":"+0.8342107534408569","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":"Q879396$D92D0254-ACD0-4A1B-99FA-EF88721A7346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d9cd2b74629fdf936558fe88cdbf1f1cf0b06bd","datavalue":{"value":{"entity-type":"item","numeric-id":1869215,"id":"Q1869215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e814af0c2ca425285b01b988fdd6a2c1821c045d","datavalue":{"value":{"amount":"+0.8328782320022583","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":"Q879396$09DFA760-C504-4FAE-AC2A-D429D5937019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcecb3c8e8c5232b9979769af814c3a54a3e9ec4","datavalue":{"value":{"entity-type":"item","numeric-id":2981333,"id":"Q2981333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e814af0c2ca425285b01b988fdd6a2c1821c045d","datavalue":{"value":{"amount":"+0.8328782320022583","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":"Q879396$61E21547-D3DE-42EE-8A0C-1509A3C7D45E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21bae4eb2bc3f6d0b6195e53876db766372847c3","datavalue":{"value":{"entity-type":"item","numeric-id":4820810,"id":"Q4820810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3ee1bd471c06a3d6b774d5e9a9b6d05e5756e34","datavalue":{"value":{"amount":"+0.820152997970581","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":"Q879396$F5702916-BA54-49DF-84AA-A7AC6E058C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"760c6944e828400c22df1f6dfee140e4285fc1d0","datavalue":{"value":{"entity-type":"item","numeric-id":3439437,"id":"Q3439437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a39cd690a3027528ebaf3b5a3fec9d2b2ade51","datavalue":{"value":{"amount":"+0.8171687126159668","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":"Q879396$80DF57D9-E1F3-47A9-A4D3-DE4B3FA1DB84","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs with small boundary","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_with_small_boundary"}}}}}