{"entities":{"Q4656572":{"pageid":6686153,"ns":120,"title":"Item:Q4656572","lastrevid":109500995,"modified":"2026-11-12T17:37:32Z","type":"item","id":"Q4656572","labels":{"en":{"language":"en","value":"Graphs whose minimal rank is two"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2144317"}},"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":"Q4656572$2A51CDDE-1E7F-4212-B060-CC807548FE3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"15afd2e7d66038121f7b2e1845f1989618909827","datavalue":{"value":{"text":"Graphs whose minimal rank is two","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4656572$9E061DE1-072A-4A95-B344-7CACED182F44","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"44c7e9e43f07edb051b7f5f81054ab1c7b7ab30a","datavalue":{"value":"1070.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$495D0C07-8D08-4B6D-A18B-631197E5ED51","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6fd7c812cf69eb242aab61d05264069c047a52eb","datavalue":{"value":"10.13001/1081-3810.1137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$9EB733DB-E3C0-4F84-B7C4-5F5D0EA03084","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8f253e1988b0b551964935f39c7c03fcedd39f4","datavalue":{"value":{"entity-type":"item","numeric-id":417527,"id":"Q417527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4656572$EB271885-6F9A-4B6B-AB94-F196E8C1F06F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"85b06cdf94912599b91283a9165869de2482d7c0","datavalue":{"value":{"entity-type":"item","numeric-id":269305,"id":"Q269305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4656572$A5765C79-1E9B-4362-8559-0973A42D777D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de4d5318c8b13daf21f1840cb3fee28230b1d04d","datavalue":{"value":{"entity-type":"item","numeric-id":594164,"id":"Q594164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4656572$D68FFC82-F002-4164-9B03-5642288495FD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3545175870bcf429dcf46f704e85b1c420feb2ed","datavalue":{"value":{"entity-type":"item","numeric-id":2701753,"id":"Q2701753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4656572$CCE779A4-B008-4BF0-B846-697867303917","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a1e9f97959c3a0c8005f0f6e1f91f49b76b5347","datavalue":{"value":{"time":"+2005-03-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":"Q4656572$067E3DA7-A4A3-4390-AFF5-2BF41FC47065","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8ff7aa4f347ba9f428744fefb33e6d3e48209eb8","datavalue":{"value":"https://eudml.org/doc/125039","type":"string"},"datatype":"url"},"type":"statement","id":"Q4656572$827AF6AC-589B-43F3-A414-93D6DB0CABEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"39b77c77a30b28d4342de38a1a35d20edb23391c","datavalue":{"value":"http://www.emis.de/journals/ELA/ela-articles/11.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q4656572$A47655EE-A6E1-4072-9F9D-F62CD83B71C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"fb92cc97f90d5f816a3d2cd475a649fa6e5dded8","datavalue":{"value":"https://semanticscholar.org/paper/529fcb9fe5bb91829cb327c91f7db4283f797db9","type":"string"},"datatype":"url"},"type":"statement","id":"Q4656572$37A64DE3-5D29-466B-BEEC-011D6E1B17EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$A6F522BD-3FA8-4504-B432-D67BB242E9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$6B6850EC-8375-4D34-A0B6-4309A9A07B94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ba5f7486cfb64f062d1b1d8e48f356198d5bc8e7","datavalue":{"value":"15A03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$640F32A6-49B9-4E0C-B651-99745B03F74C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c32074a6a9b33f3199d7f4946756883fac565aa0","datavalue":{"value":"15B57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$3523729A-7ABF-4BFB-B158-9811C36758AB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5d526cc5e52ea6b5abd90350b47f77c69d31d36c","datavalue":{"value":"2144317","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$95C54A6F-ADB2-4AE0-8804-0D7893B1DC92","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63b8c671c286f8d9fe4175c501f40bcdb34dd627","datavalue":{"value":"rank 2","type":"string"},"datatype":"string"},"type":"statement","id":"Q4656572$A3932DEB-9D97-47D6-8B30-0F5C502CC7BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd2a96e22263ec0cb91382064d48de55d6383645","datavalue":{"value":"minimum rank","type":"string"},"datatype":"string"},"type":"statement","id":"Q4656572$CA1158F0-579F-447A-A4B6-7B483DE42FCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a04ce804c98ace4c348009c4343be22d21d076c","datavalue":{"value":"symmetric matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q4656572$6681073C-7153-4839-9D77-9CF17375772A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1db4e3cd8c6237e3b25098b483a3ff821c3b321","datavalue":{"value":"forbidden subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4656572$FB8B1A30-DA12-4C62-A903-214C82F16AF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d1408278a74b260fb5c596e3c4d04ee0c56e73b","datavalue":{"value":"bilinear symmetric form","type":"string"},"datatype":"string"},"type":"statement","id":"Q4656572$D4B0E1D3-AC34-4B07-A1EE-1D1176715DFA","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":"Q4656572$E37C2EA0-57CF-4B38-8685-35D111A1CA1B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f196eabd78cab4307076300811aad00e0e669458","datavalue":{"value":"W1584938588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$216FFAAF-1EC3-4503-A0F4-AC5B0FEE4342","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"da8b955aa4fc2f4ec05b925cee788ff114928f4a","datavalue":{"value":"bafkreiacwwasbqbakc5yjkzpzwawzjezg2eedirqnzsxiabbuggrfaau3e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4656572$C2C02252-BFF8-4FB8-AF6C-A49A3FE2FFE8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e38d1536fa0b861038f949aa01382d9810d28ee","datavalue":{"value":{"entity-type":"item","numeric-id":4656586,"id":"Q4656586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa95b49b63a03a69b822da7b3617fec48af029ba","datavalue":{"value":{"amount":"+0.8897892832756042","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":"Q4656572$59B6B7EF-0B16-4FBC-83ED-22DC57D0CE4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25667060163c33c5b8bb33755c9df479cd594f18","datavalue":{"value":{"entity-type":"item","numeric-id":3497853,"id":"Q3497853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"928e7197bc307cee3bac5f944feec06694c7ddb7","datavalue":{"value":{"amount":"+0.8392924070358276","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":"Q4656572$65DC9445-3D14-463F-AF6E-ECA9108A0B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"960c4aea8420eba1b82d41ef0fd96b50f445ed3d","datavalue":{"value":{"entity-type":"item","numeric-id":3091567,"id":"Q3091567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc205115c841e775b5b0986d679dd39ef687433b","datavalue":{"value":{"amount":"+0.8353126645088196","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":"Q4656572$1CBEDEA0-16F6-43E1-B7AC-D68CEAB358AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe853403c27a86a697be890b3ff52cb57d881473","datavalue":{"value":{"entity-type":"item","numeric-id":999773,"id":"Q999773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8ef17caf85afb5ee16135685900670976a3a658","datavalue":{"value":{"amount":"+0.8316103219985962","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":"Q4656572$ECBF49BB-5826-4B14-AF49-6132531B68C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0deae3e34c703808d5cc2c896dad1091c1da1973","datavalue":{"value":{"entity-type":"item","numeric-id":765180,"id":"Q765180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a83ac3b36e860e664604f7209fbb8853ace997c","datavalue":{"value":{"amount":"+0.8282885551452637","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":"Q4656572$D02E422A-DDC1-4038-AFE3-9B6F58BB28B4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b9b7876c8300c45d014b912d5b286501e68d702","datavalue":{"value":"Given any field \\(F\\), let \\(\\text{char\\,}F\\) be the characteristic of \\(F\\), let \\(F^*\\) be the non-zero elements of \\(F\\), and let \\(F^n= \\{[x_1,\\dots, x_n]^t\\mid x_1,\\dots, x_n\\in F\\}\\). Moreover, if a (simple, undirected) graph \\(G= (V,E)\\) with vertex set \\(V= \\{1,2,\\dots, n\\}\\) is given, let \\(S(F,G)\\) be the set of all symmetric \\(n\\times n\\) matrices \\(A= [a_{ij}]\\) with entries in \\(F\\) such that \\(a_{ij}\\neq 0\\), \\(i\\neq j\\), if and only if \\(ij\\in E\\). There is no restriction on the diagonal entries of \\(A\\). In the present comprehensive paper the problem of minimizing the rank for all \\(A\\in S(F,G)\\) is studied: \\(mr(F,G)\\) is defined as \\(\\min\\{\\text{rank\\,}A\\mid A\\in S(F,G)\\}\\). In the paper all graphs in \\(S(F,G)\\) are identified for which \\(mr(F,G)\\leq 2\\) holds for any infinite field \\(F\\). In the special case \\(F= \\mathbb{R}\\) instead of \\(mr(F,G)\\) and \\(S(F,G)\\) the abbreviations \\(mr(G)\\) and \\(S(G)\\) are applied, respectively, and it is already known that here minimizing the rank is equivalent to maximizing the multiplicity of an eigenvalue of \\(A\\in S(G)\\). In the first chapter of the paper graph-theoretical concepts are introduced and some relations between certain graphs and \\(mr(F,G)\\) are given by observations: e.g. Observation \\(1: mr(F,G)= 1\\) if and only if \\(G= K_m\\cup K_{n-m}\\), \\(m\\geq 2\\) (\\(K\\) complete graph, \\(K^c\\) complement of \\(K\\)), and in particular, if \\(G\\) is connected, we have \\(mr(F,G)= 1\\) if and only if \\(G\\) is complete. From Observations 3 and 4 follows that four given graphs on four vertices (figures in the paper: diamond, paw, \\(C_4\\), claw) all have minimum rank in any field. In Chapter 2 six forbidden subgraphs for the minimum rank 2 are identified (figures in the paper) and this yields the following result: Let \\(F\\) be a field. Then holds rank 3 for five of these forbidden graphs in any field and Observation 6 reads: \\[ mr(F, K_{3,3,3})= \\begin{cases} 3\\;&\\text{if char\\,}F\\neq 2,\\\\ 2\\;&\\text{if char\\,}F= 2.\\end{cases} \\] In Chapter 4 the concept of isotropic line is used, and in Chapter 3 nondegenerate, bilinear, symmetric forms on \\(F^2\\) are introduced. A line \\(L\\) in \\(F^2\\) is a one-dimensional subspace of \\(F^2\\). By \\(S_2(F)\\) the set of the symmetric \\(2\\times 2\\) matrices over \\(F\\) is denoted. Let \\(B= [b_{ij}]\\in S_2(F)\\) be an invertible matrix over \\(F\\) which defines a nondegenerate, bilinear symmetric form \\[ (x, y)\\to x^t By,\\quad x,y\\in F^2. \\] A line \\(L\\) with the property \\(L^\\perp= L\\) is called isotropic (\\(L^\\perp\\) is the orthogonal complement of \\(L\\) in \\(F^2\\)). With this in Chapter 4 all graphs in \\(S(F,G)\\) for which \\(mr(F,G)\\leq 2\\), for any infinite fields are identified and it is shown that the complements of such graphs have a simple explicit form. The following results are proved for infinite fields \\(F\\): Theorem 1. If \\(\\text{char\\,}F\\neq 2\\), then \\(G^c\\) is of the given form (4.1). If \\(\\text{char\\,}F= 2\\), then \\(G^c\\) is either of the given form (4.2) or of the given form (4.3). Theorem 2. Let \\(F\\) be an infinite field. (1) If \\(\\text{char\\,}\\Gamma\\neq 2\\), let \\(G\\) be any graph whose complement is of the given form (4.1). (2) If \\(\\text{char\\,}F= 2\\), let \\(G\\) be any graph whose complement is of the given form (4.2) or (4.3). Then \\(mr(F,G)\\leq 2\\). (This theorem is false if \\(F\\) is finite.) By combining these two theorems together with other theorems, collaries, lemmatas and propositions the authors get further forbidden subgraph characterizations of this class of graphs. For example, Theorem 6 by combining Theorems 1, 2 \\((\\text{char\\,} F\\neq 2)\\) and \\(5\\), Theorem 7 by combining Theorems 1, 2 \\((\\text{char\\,} F =2)\\) and the complements of the graphs in Corollary 4, Theorem 9 follows from Theorem 6 in the connected case, Theorem 10 follows from Theorem 7 in the connected case. All these and further theorems are given by equivalence formulations. In the final chapter, Chapter 6, the graphs \\(G\\) are characterized for any infinite field \\(F\\) such that \\(mr(F,G)\\leq 2\\), which includes the case \\(F= \\mathbb{C}\\). Then, besides symmetric matrices with entries in \\(\\mathbb{C}\\), Hermitian matrices are studied. Now let be given a graph \\(G= (V,E)\\) with vertex set \\(V= \\{1,2,\\dots,n\\}\\), and let \\(H(G)\\) be the set of all Hermitian \\(n\\times n\\) matrices \\([a_{ij}]\\) such that \\(a_{ij}\\neq 0\\), \\(i\\neq j\\), if and only if \\(ij\\in E\\). Analogous to \\(mr(G)\\) is defined \\(hmr(G)= \\min\\{\\text{rank\\,}A\\mid A\\in H(G)\\}\\), and the inspection of the six graphs presented in Chapter 2 shows that all of them except \\(K_{3,3,3}\\) have \\(hmr(G)= 3\\), and that \\(hmr(K_{3,3,3})= 2\\). In this chapter those graphs with \\(hmr(G)\\leq 2\\) are characterized and it is shown that the forbidden subgraphs are the first five graphs presented in Chapter 2. Like in Chapter 4 the concept of isotropic line is introduced and for this the matrix \\(B\\) is replaced by a matrix of the form \\(S^*BS\\), where \\(S\\) is a \\(2\\times 2\\) invertible matrix over \\(\\mathbb{C}\\). Further theorems are proved which are partially similar to analogous theorems in previous chapters. The final result of this Chapter 6 is Theorem 16; it refers to connected graphs in the Hermitian case, and here in contrast with Theorems 9 and 10 the only forbidden subgraphs with minimal \\(\\text{rank}\\leq 2\\) are easily found.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4656572$D4510136-E00F-43CA-BE21-BA07BC86DA79","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs whose minimal rank is two","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_whose_minimal_rank_is_two"}}}}}